Decomposition of Geometric Graphs into Star Forests

2023/06/22 by János Pach, Morteza Saghafian, Pach, János +3 · 3 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #FOS: Mathematics #Markov Chains and Monte Carlo Methods

paper · pdf · doi:10.48550/arxiv.2306.13201

openalex publication_date 2023/06/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Cited by

• Decomposition of Cliques into k-Star-Forests
• Crossing and non-crossing families
• Covering Complete Geometric Graphs by Monotone Paths

Related

• Star-Forest Decompositions of Complete Graphs
• Decomposition of Cliques into k-Star-Forests
• The complexity of decomposing a graph into a matching and a bounded linear forest
• Edge Partitions of Complete Geometric Graphs (Part 1)
• On Edge-Partitioning of Complete Geometric Graphs into Plane Trees