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 条
  • [21] On the Queue Number of Planar Graphs
    Di Battista, Giuseppe
    Frati, Fabrizio
    Pach, Janos
    2010 IEEE 51ST ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, 2010, : 365 - 374
  • [22] Packing trees into planar graphs
    García, A
    Hernando, C
    Hurtado, F
    Noy, M
    Tejel, J
    JOURNAL OF GRAPH THEORY, 2002, 40 (03) : 172 - 181
  • [23] Equitable partition of planar graphs
    Kim, Ringi
    Oum, Sang-il
    Zhang, Xin
    DISCRETE MATHEMATICS, 2021, 344 (06)
  • [24] Venn diagrams and planar graphs
    Chilakamarri, KB
    Hamburger, P
    Pippert, RE
    GEOMETRIAE DEDICATA, 1996, 62 (01) : 73 - 91
  • [25] Planar character-graphs
    Ebrahimi, Mahdi
    Khatami, Maryam
    Mirzaei, Zohreh
    COMMUNICATIONS IN ALGEBRA, 2021, 49 (09) : 4079 - 4087
  • [26] PLANAR AND PROJECTIVE LINE GRAPHS OF COMAXIMAL GRAPHS OF LATTICES
    Afkhami, Mojgan
    Khashyarmanesh, Kazem
    Parsapour, Atossa
    INTERNATIONAL ELECTRONIC JOURNAL OF ALGEBRA, 2014, 16 : 72 - 88
  • [27] Fast Robber in Planar Graphs
    Nisse, Nicolas
    Suchan, Karol
    GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, 2008, 5344 : 312 - 323
  • [28] Injective coloring of planar graphs
    Bu, Yuehua
    Chen, Dong
    Raspaud, Andre
    Wang, Weifan
    DISCRETE APPLIED MATHEMATICS, 2009, 157 (04) : 663 - 672
  • [29] Extending Colorings of Planar Graphs
    Weihua Lu
    Han Ren
    Graphs and Combinatorics, 2019, 35 : 1161 - 1167
  • [30] Minimum choosability of planar graphs
    Huijuan Wang
    Bin Liu
    Ling Gai
    Hongwei Du
    Jianliang Wu
    Journal of Combinatorial Optimization, 2018, 36 : 13 - 22
12345