Abstract
We study the following problem: Given a set S of n distinct points in the plane, how many edge-disjoint plane straight-line spanning paths of S can one draw? While each spanning path is crossing-free, the edges of distinct paths may cross each other (i.e., they may intersect at points that are not elements of S). A well-known result is that when the n points are in convex position, \(\lfloor n/2\rfloor \) such paths always exist, but when the points of S are in general position the only known construction gives rise to two edge-disjoint plane straight-line spanning paths. In this paper, we show that for any set S of at least ten points in the plane, no three of which are collinear, one can draw at least three edge-disjoint plane straight-line spanning paths of S. Our proof is based on a structural theorem on halving lines of point configurations and a strengthening of the theorem about two spanning paths, which we find interesting in its own right: if S has at least six points, and we prescribe any two points on the boundary of its convex hull, then the set contains two edge-disjoint plane spanning paths starting at the prescribed points.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
References
Abellanas, M., Garcia-Lopez, J., Hernández-Peñalver, G., Noy, M., Ramos, P.A.: Bipartite embeddings of trees in the plane. Discret. Appl. Math. 93(2–3), 141–148 (1999). https://doi.org/10.1016/S0166-218X(99)00042-6
Aichholzer, O., et al.: Packing plane spanning trees and paths in complete geometric graphs. Inf. Process. Lett. 124, 35–41 (2017). https://doi.org/10.1016/j.ipl.2017.04.006
Bernhart, F., Kainen, P.C.: The book thickness of a graph. J. Comb. Theory, Ser. B 27(3), 320–331 (1979). https://doi.org/10.1016/0095-8956(79)90021-2
Bollobás, B., Eldridge, S.E.: Packings of graphs and applications to computational complexity. J. Comb. Theory Ser. B 25(2), 105–124 (1978). https://doi.org/10.1016/0095-8956(78)90030-8
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). https://doi.org/10.1016/j.comgeo.2005.08.006
Geyer, M., Hoffmann, M., Kaufmann, M., Kusters, V., Tóth, C.D.: The planar tree packing theorem. J. Comput. Geom. 8(2), 109–177 (2017). https://doi.org/10.20382/jocg.v8i2a6
Haler, S.P., Wang, H.: Packing four copies of a tree into a complete graph. Australas. J. Comb. 59, 323–332 (2014). http://ajc.maths.uq.edu.au/pdf/59/ajc_v59_p323.pdf
Hedetniemi, S.M., Hedetniemi, S.T., Slater, P.J.: A note on packing two trees into \(k_n\). Ars Combin. 11, 149–153 (1981)
Hershberger, J., Suri, S.: Applications of a semi-dynamic convex hull algorithm. BIT 32(2), 249–267 (1992). https://doi.org/10.1007/BF01994880
Kindermann, P., Kratochvíl, J., Liotta, G., Valtr, P.: Three edge-disjoint plane spanning paths in a point set. Arxiv report 2306.07237 (2023). https://doi.org/10.48550/arXiv.2306.07237
Luca, F.D., et al.: Packing trees into 1-planar graphs. J. Graph Algorithms Appl. 25(2), 605–624 (2021). https://doi.org/10.7155/jgaa.00574
Scheucher, M.: Personal communication
Teo, S.K., Yap, H.P.: Packing two graphs of order n having total size at most 2n–2. Graphs Comb. 6(2), 197–205 (1990). https://doi.org/10.1007/BF01787731
Acknowledgments
The second and fourth authors gratefully acknowledge the support of Czech Science Foundation through research grant GAČR 23-04949X. The work of the third author is partially supported by “ (i) MUR PRIN Proj. 2022TS4Y3N - “EXPAND: scalable algorithms for EXPloratory Analyses of heterogeneous and dynamic Networked Data”; (ii) MUR PRIN Proj. 2022ME9Z78 - “NextGRAAL: Next-generation algorithms for constrained GRAph visuALization”. All authors acknowledge the working atmosphere of Homonolo meetings where the research was initiated and part of the results were obtained, as well as of Bertinoro Workshops on Graph Drawing, during which we could meet and informally work on the project. Our special thanks go to Manfred Scheucher whose experimental results encouraged us to keep working on the problem in the time when all hopes for a solution seemed far out of sight.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Kindermann, P., Kratochvíl, J., Liotta, G., Valtr, P. (2023). Three Edge-Disjoint Plane Spanning Paths in a Point Set. In: Bekos, M.A., Chimani, M. (eds) Graph Drawing and Network Visualization. GD 2023. Lecture Notes in Computer Science, vol 14465. Springer, Cham. https://doi.org/10.1007/978-3-031-49272-3_22
Download citation
DOI: https://doi.org/10.1007/978-3-031-49272-3_22
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-49271-6
Online ISBN: 978-3-031-49272-3
eBook Packages: Computer ScienceComputer Science (R0)