research article
Decomposition of geometric graphs into star-forests
December 1, 2025
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.
Type
research article
Scopus ID
2-s2.0-105001555771
Author(s)
École Polytechnique Fédérale de Lausanne
Saghafian, Morteza
Institute of Science and Technology Austria (ISTA)
Schnider, Patrick
ETH Zürich
Date Issued
2025-12-01
Published in
Volume
129
Article Number
102186
Editorial or Peer reviewed
REVIEWED
Written at
EPFL
EPFL units
| Funder | Funding(s) | Grant Number | Grant URL |
Hungarian Science Foundation | |||
Institute of Science and Technology Austria | |||
European Research Council | 882971 | ||
| Show more | |||
Available on Infoscience
April 11, 2025
Use this identifier to reference this record