Decomposition of Geometric Graphs into Star Forests

DOI10.1007/978-3-031-49272-3_23MaRDI QIDQ6441182zbMATH OpenWikidataFDO

Authors János Pach, Morteza Saghafian, Patrick Schnider

Publication date 22 June 2023

Full work available at URL https://doi.org/10.1007/978-3-031-49272-3_23

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: We solve a problem of Dujmovi'c 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 in

(4)

• Star-forest decompositions of complete graphs
• Covering complete geometric graphs by monotone paths
• Partitioning complete geometric graphs on dense point sets into plane subgraphs
• Partitioning complete geometric graphs on dense point sets into plane subgraphs

This page was built for publication: Decomposition of Geometric Graphs into Star Forests

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6441182)