Abstract
Consider the following open problem: 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.
Original language  English 

Title of host publication  Graph Drawing 
Subtitle of host publication  12th International Symposium, GD 2004 New York, NY, USA, September 29October 2, 2004 Revised Selected Papers 
Editors  János Pach 
Place of Publication  Berlin Germany 
Publisher  Springer 
Pages  7181 
Number of pages  11 
ISBN (Print)  3540245286 
DOIs  
Publication status  Published  1 Dec 2004 
Externally published  Yes 
Event  Graph Drawing 2004  New York, United States of America Duration: 29 Sep 2004 → 2 Oct 2004 Conference number: 12th https://link.springer.com/book/10.1007/b105810 (Proceedings) 
Publication series
Name  Lecture Notes in Computer Science 

Publisher  Springer 
Volume  3383 
ISSN (Print)  03029743 
Conference
Conference  Graph Drawing 2004 

Abbreviated title  GD 2004 
Country/Territory  United States of America 
City  New York 
Period  29/09/04 → 2/10/04 
Internet address 
