Decomposition of Geometric Graphs into Star Forests

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.

Appears in the Proceedings of the 31st International Symposium on Graph Drawing and Network Visualization (GD 2023)