On some packing and partition problems in geometric graphs
Graph packing problem refers to the problem of finding maximum number of edge-disjoint copies of a fixed subgraph in a given graph G. A related problem is the partition problem. In this case, the edge-disjoint subgraphs are sought but require that the union of subgraphs in this packing is exactly...
| Main Author: | |
|---|---|
| Format: | Thesis |
| Language: | English |
| Published: |
2018
|
| Subjects: | |
| Online Access: | http://psasir.upm.edu.my/id/eprint/76910/ http://psasir.upm.edu.my/id/eprint/76910/1/FS%202018%2085%20-%20IR.pdf |
| _version_ | 1848858102025158656 |
|---|---|
| author | Trao, Hazim Michman |
| author_facet | Trao, Hazim Michman |
| author_sort | Trao, Hazim Michman |
| building | UPM Institutional Repository |
| collection | Online Access |
| description | Graph packing problem refers to the problem of finding maximum number of
edge-disjoint copies of a fixed subgraph in a given graph G. A related problem is
the partition problem. In this case, the edge-disjoint subgraphs are sought but
require that the union of subgraphs in this packing is exactly G. It is often useful
to restrict the subgraphs of G to a certain graph or property.
In this thesis, packing and partition problems are studied for different
properties such as matching, tree and cycle, and these problems are considered
in various geometric graphs. The families of geometric graphs that are
investigated include the complete geometric graphs, triangle-free geometric
graphs, and complete bipartite geometric graphs.
First, the problem of partitioning the complete geometric graph into plane
spanning trees is investigated, giving sufficient conditions, which generalize the
convex case and the wheel configuration case.
The problem of packing plane perfect matchings is studied in triangle-free
geometric graphs where we establish lower and upper bounds for the problem.
An algorithm for computing such plane perfect matchings is also presented.
Moreover, a sufficient condition is provided for the existence the set of
edge-disjoint plane perfect matchings whose union is a maximal triangle-free
geometric graph.
Furthermore, the problem of partitioning the complete bipartite geometric graphs
into plane perfect matchings is studied and sufficient conditions for the problem
are presented.
Finally, the problem of packing 1-plane Hamiltonian cycles into the complete
geometric graph is studied in order to establish lower and upper bounds for the
problem. An algorithm for computing such 1-plane Hamiltonian cycles is also
presented. |
| first_indexed | 2025-11-15T12:08:06Z |
| format | Thesis |
| id | upm-76910 |
| institution | Universiti Putra Malaysia |
| institution_category | Local University |
| language | English |
| last_indexed | 2025-11-15T12:08:06Z |
| publishDate | 2018 |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | upm-769102020-02-11T01:20:54Z http://psasir.upm.edu.my/id/eprint/76910/ On some packing and partition problems in geometric graphs Trao, Hazim Michman Graph packing problem refers to the problem of finding maximum number of edge-disjoint copies of a fixed subgraph in a given graph G. A related problem is the partition problem. In this case, the edge-disjoint subgraphs are sought but require that the union of subgraphs in this packing is exactly G. It is often useful to restrict the subgraphs of G to a certain graph or property. In this thesis, packing and partition problems are studied for different properties such as matching, tree and cycle, and these problems are considered in various geometric graphs. The families of geometric graphs that are investigated include the complete geometric graphs, triangle-free geometric graphs, and complete bipartite geometric graphs. First, the problem of partitioning the complete geometric graph into plane spanning trees is investigated, giving sufficient conditions, which generalize the convex case and the wheel configuration case. The problem of packing plane perfect matchings is studied in triangle-free geometric graphs where we establish lower and upper bounds for the problem. An algorithm for computing such plane perfect matchings is also presented. Moreover, a sufficient condition is provided for the existence the set of edge-disjoint plane perfect matchings whose union is a maximal triangle-free geometric graph. Furthermore, the problem of partitioning the complete bipartite geometric graphs into plane perfect matchings is studied and sufficient conditions for the problem are presented. Finally, the problem of packing 1-plane Hamiltonian cycles into the complete geometric graph is studied in order to establish lower and upper bounds for the problem. An algorithm for computing such 1-plane Hamiltonian cycles is also presented. 2018-07 Thesis NonPeerReviewed text en http://psasir.upm.edu.my/id/eprint/76910/1/FS%202018%2085%20-%20IR.pdf Trao, Hazim Michman (2018) On some packing and partition problems in geometric graphs. Doctoral thesis, Universiti Putra Malaysia. Graphic methods Mathematics |
| spellingShingle | Graphic methods Mathematics Trao, Hazim Michman On some packing and partition problems in geometric graphs |
| title | On some packing and partition problems in geometric graphs |
| title_full | On some packing and partition problems in geometric graphs |
| title_fullStr | On some packing and partition problems in geometric graphs |
| title_full_unstemmed | On some packing and partition problems in geometric graphs |
| title_short | On some packing and partition problems in geometric graphs |
| title_sort | on some packing and partition problems in geometric graphs |
| topic | Graphic methods Mathematics |
| url | http://psasir.upm.edu.my/id/eprint/76910/ http://psasir.upm.edu.my/id/eprint/76910/1/FS%202018%2085%20-%20IR.pdf |