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 条
  • [21] Local properties of geometric graphs
    Cardinal, Jean
    Collette, Sebastien
    Langerman, Stefan
    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2008, 39 (01): : 55 - 64
  • [22] Infinite Random Geometric Graphs
    Anthony Bonato
    Jeannette Janssen
    Annals of Combinatorics, 2011, 15 : 597 - 617
  • [23] Distance measures for geometric graphs
    Majhi, Sushovan
    Wenk, Carola
    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2024, 118
  • [24] A note on light geometric graphs
    Ackerman, Eyal
    Fox, Jacob
    Pinchasi, Rom
    DISCRETE MATHEMATICS, 2013, 313 (12) : 1281 - 1283
  • [25] Star Coloring of Sparse Graphs
    Bu, Yuehua
    Cranston, Daniel W.
    Montassier, Mickael
    Raspaud, Andre
    Wang, Weifan
    JOURNAL OF GRAPH THEORY, 2009, 62 (03) : 201 - 219
  • [26] Duality in Geometric Graphs: Vector Graphs, Kirchhoff Graphs and Maxwell Reciprocal Figures
    Reese, Tyler
    Paffenroth, Randy
    Fehribach, Joseph D.
    SYMMETRY-BASEL, 2016, 8 (03):
  • [27] THE TURN NUMBER OF SPANNING STAR FORESTS
    Zhang, Lin-peng
    Wang, Ligong
    Zhou, Jiale
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2023, 43 (02) : 303 - 312
  • [28] On crossing numbers of geometric proximity graphs
    Abrego, Bernardo M.
    Fabila-Monroy, Ruy
    Fernandez-Merchant, Silvia
    Flores-Penaloza, David
    Hurtado, Ferran
    Sacristan, Vera
    Saumell, Maria
    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2011, 44 (04): : 216 - 233
  • [29] Counting the number of crossings in geometric graphs
    Duque, Frank
    Fabila-Monroy, Ruy
    Hernandez-Velez, Cesar
    Hidalgo-Toscano, Carlos
    INFORMATION PROCESSING LETTERS, 2021, 165
  • [30] New production matrices for geometric graphs
    Esteban, Guillermo
    Huemer, Clemens
    Silveira, Rodrigo, I
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2022, 633 : 244 - 280
12345