Decomposition of geometric graphs into star-forests

被引：0
|
作者：
Pach, Jano [1 ,2 ]
Saghafian, Morteza [3 ]
Schnider, Patrick [4 ]
机构：
[1] Renyi Inst Math, Budapest, Hungary
[2] EPFL Ecole Polytech Fed Lausanne, Lausanne, Switzerland
[3] ISTA Inst Sci & Technol Austria, Klosterneuburg, Austria
[4] Swiss Fed Inst Technol, Dept Comp Sci, Zurich, Switzerland
来源：
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | 2025年 / 129卷
基金：
欧洲研究理事会; 奥地利科学基金会;
关键词：
Geometric graphs; Graph decomposition; Graph thickness; Star forests;
D O I：
10.1016/j.comgeo.2025.102186
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
We solve a problem of Dujmovic<acute accent> 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. (c) 2025 Published by Elsevier B.V.
引用
收藏
页数：6
相关论文
共 50 条
  • [31] Decomposition of Complete Graphs into Isomorphic Complete Bipartite Graphs
    Kolotoglu, Emre
    JOURNAL OF COMBINATORIAL DESIGNS, 2013, 21 (11) : 524 - 530
  • [32] Packing plane spanning graphs with short edges in complete geometric graphs
    Aichholzer, Oswin
    Hackl, Thomas
    Korman, Matias
    Pilz, Alexander
    van Renssen, Andre
    Roeloffzen, Marcel
    Rote, Gunter
    Vogtenhuber, Birgit
    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2019, 82 (1-15): : 1 - 15
  • [33] A Polynomial Bound for Untangling Geometric Planar Graphs
    Prosenjit Bose
    Vida Dujmović
    Ferran Hurtado
    Stefan Langerman
    Pat Morin
    David R. Wood
    Discrete & Computational Geometry, 2009, 42 : 570 - 585
  • [34] A Polynomial Bound for Untangling Geometric Planar Graphs
    Bose, Prosenjit
    Dujmovic, Vida
    Hurtado, Ferran
    Langerman, Stefan
    Morin, Pat
    Wood, David R.
    DISCRETE & COMPUTATIONAL GEOMETRY, 2009, 42 (04) : 570 - 585
  • [35] Bounds on the crossing resolution of complete geometric graphs
    Di Giacomo, Emilio
    Didimo, Walter
    Eades, Peter
    Hong, Seok-Hee
    Liotta, Giuseppe
    DISCRETE APPLIED MATHEMATICS, 2012, 160 (1-2) : 132 - 139
  • [36] Intersection number of two connected geometric graphs
    Tokunaga, S
    INFORMATION PROCESSING LETTERS, 1996, 59 (06) : 331 - 333
  • [37] Geometric Biplane Graphs II: Graph Augmentation
    Garcia, Alfredo
    Hurtado, Ferran
    Korman, Matias
    Matos, Ines
    Saumell, Maria
    Silveira, Rodrigo I.
    Tejel, Javier
    Toth, Csaba D.
    GRAPHS AND COMBINATORICS, 2015, 31 (02) : 427 - 452
  • [38] Geometric Biplane Graphs II: Graph Augmentation
    Alfredo García
    Ferran Hurtado
    Matias Korman
    Inês Matos
    Maria Saumell
    Rodrigo I. Silveira
    Javier Tejel
    Csaba D. Tóth
    Graphs and Combinatorics, 2015, 31 : 427 - 452
  • [39] Edge decomposition of complete tripartite graphs
    Edwards, K
    DISCRETE MATHEMATICS, 2003, 272 (2-3) : 269 - 275
  • [40] DECOMPOSITION OF COMPLETE GRAPHS INTO TRIANGLES AND CLAWS
    Fu, Chin-Mei
    Lin, Yuan-Lung
    Lo, Shu-Wen
    Hsu, Yu-Fong
    TAIWANESE JOURNAL OF MATHEMATICS, 2014, 18 (05): : 1563 - 1581
12345