×

Packing plane spanning trees and paths in complete geometric graphs. (English) Zbl 1416.05219

Summary: We consider the following question: How many edge-disjoint plane spanning trees are contained in a complete geometric graph \(GK_n\) on any set \(S\) of \(n\) points in general position in the plane? We show that this number is in \(\Omega(\sqrt n)\). Further, we consider variants of this problem by bounding the diameter and the degree of the trees (in particular considering spanning paths).

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C05 Trees
05C38 Paths and cycles
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Abellanas, M.; Garcia-Lopez, J.; Hernández-Peñalver, G.; Noy, M.; Ramos, P. A., Bipartite embeddings of trees in the plane, Discrete Appl. Math., 93, 2-3, 141-148 (1999) · Zbl 0929.05021
[2] Aichholzer, O., Order types, Last retrieved on May 7, 2014
[3] Aichholzer, O.; Aurenhammer, F.; Krasser, H., Enumerating order types for small point sets with applications, Order, 19, 265-281 (2002) · Zbl 1027.68127
[4] Aichholzer, O.; Cabello, S.; Fabila Monroy, R.; Flores-Peñaloza, D.; Hackl, T.; Huemer, C.; Hurtado, F.; Wood, D. R., Edge-removal and non-crossing configurations in geometric graphs, Discrete Math. Theor. Comput. Sci., 12, 1, 75-86 (2010) · Zbl 1250.05060
[5] Aronov, B.; Erdős, P.; Goddard, W.; Kleitman, D. J.; Klugerman, M.; Pach, J.; Schulman, L. J., Crossing families, Combinatorica, 14, 2, 127-134 (1994) · Zbl 0804.52010
[6] Bernhart, F.; Kainen, P. C., The book thickness of a graph, J. Comb. Theory, Ser. B, 27, 3, 320-331 (1979) · Zbl 0427.05028
[7] Bose, P.; Hurtado, F.; Rivera-Campo, E.; Wood, D. R., Partitions of complete geometric graphs into plane trees, Comput. Geom., 34, 2, 116-125 (2006) · Zbl 1091.05018
[8] Černý, J., Geometric graphs with no three disjoint edges, Discrete Comput. Geom., 34, 4, 679-695 (2005) · Zbl 1081.05078
[9] Černý, J.; Dvorak, Z.; Jelínek, V.; Kára, J., Noncrossing Hamiltonian paths in geometric graphs, Discrete Appl. Math., 155, 9, 1096-1105 (2007) · Zbl 1120.05051
[10] Dillencourt, M. B.; Eppstein, D.; Hirschberg, D. S., Geometric thickness of complete graphs, J. Graph Algorithms Appl., 4, 3, 5-17 (2000) · Zbl 0955.05028
[11] Erdős, P., On sets of distances of \(n\) points, Am. Math. Mon., 77, 7, 738-740 (1970)
[13] Hershberger, J.; Suri, S., Applications of a semi-dynamic convex hull algorithm, BIT, 32, 2, 249-267 (1992) · Zbl 0761.68097
[14] Károlyi, G.; Pach, J.; Tóth, G., Ramsey-type results for geometric graphs, I, Discrete Comput. Geom., 18, 3, 247-255 (1997) · Zbl 0940.05046
[15] Keller, C.; Perles, M. A.; Rivera-Campo, E.; Urrutia-Galicia, V., Blockers for noncrossing spanning trees in complete geometric graphs, (Pach, J., Thirty Essays on Geometric Graph Theory. Thirty Essays on Geometric Graph Theory, Algorithms Comb., vol. 29 (2012), Springer), 383-398 · Zbl 1272.05026
[16] Kundu, S., Bounds on the number of disjoint spanning trees, J. Comb. Theory, Ser. B, 17, 2, 199-203 (1974) · Zbl 0285.05113
[17] Nash-Williams, C. St. J.A., Edge-disjoint spanning trees of finite graphs, J. Lond. Math. Soc., 36, 445-450 (1961) · Zbl 0102.38805
[18] Pilz, A.; Welzl, E., Order on order types, (Proc. 31st International Symposium on Computational Geometry. Proc. 31st International Symposium on Computational Geometry, SoCG 2015 (2015)), 285-299 · Zbl 1378.68184
[19] Rivera-Campo, E., A note on the existence of plane spanning trees of geometric graphs, (Akiyama, J.; Kano, M.; Urabe, M., JCDCG. JCDCG, Lect. Notes Comput. Sci., vol. 1763 (1998), Springer), 274-277 · Zbl 0956.05030
[20] Schnider, P., Packing plane spanning double stars into complete geometric graphs, (Proc. 32nd European Workshop on Computational Geometry. Proc. 32nd European Workshop on Computational Geometry, EuroCG ’16 (2016)), 91-94
[21] Tóth, G.; Valtr, P., Geometric graphs with few disjoint edges, Discrete Comput. Geom., 22, 4, 633-642 (1999) · Zbl 0939.68097
[22] Tutte, W. T., On the problem of decomposing a graph into \(n\) connected factors, J. Lond. Math. Soc., 36, 221-230 (1961) · Zbl 0096.38001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.