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 条
  • [41] Decomposition of Complete Graphs into Arbitrary Trees
    G. Sethuraman
    V. Murugan
    Graphs and Combinatorics, 2021, 37 : 1191 - 1203
  • [42] Decomposition of Complete Graphs into Cycles and Stars
    Shyu, Tay-Woei
    GRAPHS AND COMBINATORICS, 2013, 29 (02) : 301 - 313
  • [43] Star-Forest Decompositions of Complete Graphs
    Antic, Todor
    Glisic, Jelena
    Milivojcevic, Milan
    COMBINATORIAL ALGORITHMS, IWOCA 2024, 2024, 14764 : 126 - 137
  • [44] Decomposition of Complete Graphs into Cycles and Stars
    Tay-Woei Shyu
    Graphs and Combinatorics, 2013, 29 : 301 - 313
  • [45] Graph decomposition approaches for terminology graphs
    Biha, Mohamed Didi
    Kaba, Bangaly
    Meurs, Marie-Jean
    SanJuan, Eric
    MICAI 2007: ADVANCES IN ARTIFICIAL INTELLIGENCE, 2007, 4827 : 883 - +
  • [46] Decomposition of Complete Graphs into Arbitrary Trees
    Sethuraman, G.
    Murugan, V.
    GRAPHS AND COMBINATORICS, 2021, 37 (04) : 1191 - 1203
  • [47] Decomposition of complete graphs into connected unicyclic bipartite graphs with eight edges
    Fahnenstiel, John
    Froncek, Dalibor
    ELECTRONIC JOURNAL OF GRAPH THEORY AND APPLICATIONS, 2019, 7 (02) : 235 - 250
  • [48] Crossing and intersecting families of geometric graphs on point sets
    Alvarez-Rebollar, J. L.
    Cravioto-Lagos, J.
    Marin, N.
    Sole-Pi, O.
    Urrutia, J.
    GRAPHS AND COMBINATORICS, 2024, 40 (01)
  • [49] On the Number of Edges in Geometric Graphs Without Empty Triangles
    Bautista-Santiago, C.
    Heredia, M. A.
    Huemer, C.
    Ramirez-Vigueras, A.
    Seara, C.
    Urrutia, J.
    GRAPHS AND COMBINATORICS, 2013, 29 (06) : 1623 - 1631
  • [50] On the Number of Edges in Geometric Graphs Without Empty Triangles
    C. Bautista-Santiago
    M. A. Heredia
    C. Huemer
    A. Ramírez-Vigueras
    C. Seara
    J. Urrutia
    Graphs and Combinatorics, 2013, 29 : 1623 - 1631
12345