Decomposition of geometric graphs into star-forests
Pach J, Saghafian M, Schnider P. 2025. Decomposition of geometric graphs into star-forests. Computational Geometry. 129, 102186.
Download (ext.)
Journal Article
| Published
| English
Author
Pach, János;
Saghafian, MortezaISTA;
Schnider, Patrick
Corresponding author has ISTA affiliation
Department
Abstract
We solve a problem of Dujmović and Wood (2007) by showing that a complete convex geometric graph on n vertices cannot be decomposed into fewer than n - 1 star-forests, each consisting of noncrossing edges. This bound is clearly tight. We also discuss similar questions for abstract graphs.
Publishing Year
Date Published
2025-12-01
Journal Title
Computational Geometry
Publisher
Elsevier
Acknowledgement
A preliminary version of this note has been published in the proceedings of the 31st International Symposium on Graph Drawing and Network Visualization, Palermo, 2023. The authors would like to thank the anonymous referees for their valuable comments.
Volume
129
Article Number
102186
ISSN
IST-REx-ID
Cite this
Pach J, Saghafian M, Schnider P. Decomposition of geometric graphs into star-forests. Computational Geometry. 2025;129. doi:10.1016/j.comgeo.2025.102186
Pach, J., Saghafian, M., & Schnider, P. (2025). Decomposition of geometric graphs into star-forests. Computational Geometry. Elsevier. https://doi.org/10.1016/j.comgeo.2025.102186
Pach, János, Morteza Saghafian, and Patrick Schnider. “Decomposition of Geometric Graphs into Star-Forests.” Computational Geometry. Elsevier, 2025. https://doi.org/10.1016/j.comgeo.2025.102186.
J. Pach, M. Saghafian, and P. Schnider, “Decomposition of geometric graphs into star-forests,” Computational Geometry, vol. 129. Elsevier, 2025.
Pach J, Saghafian M, Schnider P. 2025. Decomposition of geometric graphs into star-forests. Computational Geometry. 129, 102186.
Pach, János, et al. “Decomposition of Geometric Graphs into Star-Forests.” Computational Geometry, vol. 129, 102186, Elsevier, 2025, doi:10.1016/j.comgeo.2025.102186.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 2306.13201
Google Scholar