Pach, János and Saghafian, M. and Schnider, P. (2023) Decomposition of Geometric Graphs into Star-Forests. In: 31st International Symposium on Graph Drawing and Network Visualization, GD 2023. Lecture Notes in Computer Science (14465). Springer Science and Business Media B.V., pp. 339-346. ISBN 9783031492716
|
Text
2306.13201v2.pdf Available under License Creative Commons Attribution. Download (712kB) | Preview |
Official URL: https://doi.org/10.1007/978-3-031-49272-3_23
Abstract
We solve a problem of Dujmovi´c and Wood (2007) by show- ing that a complete convex geometric graph on n vertices cannot be de- composed 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.
| Item Type: | Book Section |
|---|---|
| Uncontrolled Keywords: | GEOMETRY; STARS; Graph decomposition; Geometric graphs; Geometric graphs; Graph decompositions; Non-crossing edges; Convex geometric graphs; Star forests; Star forest; Graph thickness; Graph thickness; |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 05 Apr 2024 09:52 |
| Last Modified: | 05 Apr 2024 09:52 |
| URI: | https://real.mtak.hu/id/eprint/191897 |
Actions (login required)
 |
Edit Item |
