On the reconstruction of planar graphs

被引：5
作者：
Bilinski, Mark
Kwon, Young Soo
Yu, Xingxing [1 ]
机构：
[1] Georgia Inst Technol, Sch Math, Atlanta, GA 30332 USA
[2] Yeungnam Univ, Dept Math, Kyongsan 712749, South Korea
[3] Nankai Univ, Ctr Combinator, LPMC, Tianjin 300071, Peoples R China
来源：
JOURNAL OF COMBINATORIAL THEORY SERIES B | 2007年 / 97卷 / 05期
基金：
中国国家自然科学基金; 美国国家科学基金会;
关键词：
reconstruction; recognition; planar graph; non-separating cycle; wheel neighborhood;
D O I：
10.1016/j.jctb.2006.12.005
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
We show that the planarity of a graph can be recognized from its vertex deleted subgraphs, which answers a question posed by Bondy and Hemminger in 1979. We also state some useful counting lemmas and use them to reconstruct certain planar graphs. (c) 2007 Elsevier Inc. All rights reserved.
引用
收藏
页码：745 / 756
页数：12
相关论文
共 50 条
  • [41] Combinatorial curvature for planar graphs
    Higuchi, Y
    JOURNAL OF GRAPH THEORY, 2001, 38 (04) : 220 - 229
  • [42] On list (p, 1)-total labellings of special planar graphs and 1-planar graphs
    Lin Sun
    Guanglong Yu
    Jianliang Wu
    Journal of Combinatorial Optimization, 2024, 47
  • [43] On list (p, 1)-total labellings of special planar graphs and 1-planar graphs
    Sun, Lin
    Yu, Guanglong
    Wu, Jianliang
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2024, 47 (03)
  • [44] k-forested choosability of planar graphs and sparse graphs
    Zhang, Xin
    Liu, Guizhen
    Wu, Jian-Liang
    DISCRETE MATHEMATICS, 2012, 312 (05) : 999 - 1005
  • [45] EXTREMAL GRAPHS AND CLASSIFICATION OF PLANAR GRAPHS BY MC-NUMBERS
    Gao, Yanhong
    LI, Ping
    LI, Xueliang
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2023, 43 (04) : 1253 - 1272
  • [46] A curvature notion for planar graphs stable under planar duality
    Akama, Yohji
    Hua, Bobo
    Su, Yanhui
    Wang, Lili
    ADVANCES IN MATHEMATICS, 2021, 385
  • [47] On stable cutsets in claw-free graphs and planar graphs
    Le, Van Bang
    Mosca, Raffaele
    Muller, Haiko
    JOURNAL OF DISCRETE ALGORITHMS, 2008, 6 (02) : 256 - 276
  • [48] Infinite paths in planar graphs I: Graphs with radial nets
    Yu, XX
    JOURNAL OF GRAPH THEORY, 2004, 47 (02) : 147 - 162
  • [49] On the recognition and reconstruction of weighted Voronoi diagrams and bisector graphs
    Eder, Guenther
    Held, Martin
    de Lorenzo, Stefan
    Palfrader, Peter
    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2023, 109
  • [50] Planar polycyclic graphs and their Tutte polynomials
    Tomislav Došlić
    Journal of Mathematical Chemistry, 2013, 51 : 1599 - 1607
12345