Partitions of complete geometric graphs into plane trees
Consider the following open problem: does every complete geometric graph K2n have a partition of its edge set into n plane spanning trees? We approach this problem from three directions. First, we study the case of convex geometric graphs. It is well known that the complete convex graph K2n has a partition into n plane spanning trees. We characterise all such partitions. Second, we give a sufficient condition, which generalises the convex case, for a complete geometric graph to have a partition into plane spanning trees. Finally, we consider a relaxation of the problem in which the trees of the partition are not necessarily spanning. We prove that every complete geometric graph Kn can be partitioned into at most n - √n/12 plane trees.
|Conference||12th International Symposium on Graph Drawing, GD 2004|
Bose, P, Hurtado, F. (Ferran), Rivera-Campo, E. (Eduarde), & Wood, D. (2004). Partitions of complete geometric graphs into plane trees. Presented at the 12th International Symposium on Graph Drawing, GD 2004.