Partitions of complete geometric graphs into plane trees

Prosenjit Bose, Ferran Hurtado, Eduarde Rivera-Campo, David R. Wood

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review


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.

Original languageEnglish
Title of host publicationGraph Drawing
Subtitle of host publication12th International Symposium, GD 2004 New York, NY, USA, September 29-October 2, 2004 Revised Selected Papers
EditorsJános Pach
Place of PublicationBerlin Germany
Number of pages11
ISBN (Print)3540245286
Publication statusPublished - 1 Dec 2004
Externally publishedYes
EventGraph Drawing 2004 - New York, United States of America
Duration: 29 Sept 20042 Oct 2004
Conference number: 12th (Proceedings)

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


ConferenceGraph Drawing 2004
Abbreviated titleGD 2004
Country/TerritoryUnited States of America
CityNew York
Internet address

Cite this