Portal de Periódicos da CAPES

Partitions of complete geometric graphs into plane trees

2005; Elsevier BV; Volume: 34; Issue: 2 Linguagem: Inglês

10.1016/j.comgeo.2005.08.006

1879-081X

Prosenjit Bose, Ferrán Hurtado, Eduardo Rivera‐Campo, David R. Wood,

Limits and Structures in Graph Theory

Consider the following question: does every complete geometric graph K 2 n 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 2 n 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.