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 条
  • [1] Decomposition of Geometric Graphs into Star-Forests
    Pach, Janos
    Saghafian, Morteza
    Schnider, Patrick
    GRAPH DRAWING AND NETWORK VISUALIZATION, GD 2023, PT I, 2023, 14465 : 339 - 346
  • [2] Classes of graphs without star forests and related graphs
    Atminas, Aistis
    DISCRETE MATHEMATICS, 2022, 345 (12)
  • [3] On decomposing regular graphs into star forests
    El-Zanati, S. I.
    Kopp, M.
    Plantholt, Michael J.
    Rice, Sabrina
    INTERNATIONAL JOURNAL OF MATHEMATICS AND COMPUTER SCIENCE, 2016, 11 (02) : 249 - 256
  • [4] ON DOUBLE-STAR DECOMPOSITION OF GRAPHS
    Akbari, Saieed
    Haghi, Shahab
    Maimani, Hamidreza
    Seify, Abbas
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2017, 37 (03) : 835 - 840
  • [5] DECOMPOSITION OF COMPLETE GRAPHS INTO FORESTS WITH SIX EDGES
    Freyberg, Bryan
    Peters, Ryan
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2024, : 677 - 689
  • [6] Decomposition of Sparse Graphs into Forests and a Graph with Bounded Degree
    Kim, Seog-Jin
    Kostochka, Alexandr V.
    West, Douglas B.
    Wu, Hehui
    Zhu, Xuding
    JOURNAL OF GRAPH THEORY, 2013, 74 (04) : 369 - 391
  • [7] Spectral extremal results on the a-index of graphs without minors and star forests
    Chen, Ming-Zhu
    Liu, A-Ming
    Zhang, Xiao-Dong
    PURE AND APPLIED MATHEMATICS QUARTERLY, 2022, 18 (06) : 2355 - 2378
  • [8] Decomposition of sparse graphs into forests: The Nine Dragon Tree Conjecture for k ≤ 2
    Chen, Min
    Kim, Seog-Jin
    Kostochka, Alexandr V.
    West, Douglas B.
    Zhu, Xuding
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2017, 122 : 741 - 756
  • [9] Decomposition of geometric constraint graphs based on computing fundamental circuits. Correctness and complexity
    Joan-Arinyo, R.
    Tarres-Puertas, M.
    Vila-Marta, S.
    COMPUTER-AIDED DESIGN, 2014, 52 : 1 - 16
  • [10] A Self-stabilizing Algorithm for Maximal p-Star Decomposition of General Graphs
    Neggazi, Brahim
    Turau, Volker
    Haddad, Mohammed
    Kheddouci, Hamamache
    STABILIZATION, SAFETY, AND SECURITY OF DISTRIBUTED SYSTEMS, SSS 2013, 2013, 8255 : 74 - 85
12345