Consider the following question: does every complete geometric graph K 2n 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 K 2n 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 K n can be partitioned into at most n-√n/12 plane trees. This is the best known bound even for partitions into plane subgraphs.

Additional Metadata
Keywords Book embedding, Book thickness, Complete graph, Convex graph, Crossing family, Geometric graph, Plane tree
Persistent URL dx.doi.org/10.1016/j.comgeo.2005.08.006
Journal Computational Geometry
Citation
Bose, P, Hurtado, F. (Ferran), Rivera-Campo, E. (Eduardo), & Wood, D. (2006). Partitions of complete geometric graphs into plane trees. Computational Geometry, 34(2), 116–125. doi:10.1016/j.comgeo.2005.08.006