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...
Saved in:
| Main Author: | |
|---|---|
| Format: | Thesis |
| Language: | English |
| Published: |
2018
|
| Subjects: | |
| Online Access: | http://psasir.upm.edu.my/id/eprint/76910/1/FS%202018%2085%20-%20IR.pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | 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. |
|---|