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 条
  • [31] On the linear arboricity of planar graphs
    Wu, JL
    JOURNAL OF GRAPH THEORY, 1999, 31 (02) : 129 - 134
  • [32] Disk Embeddings of Planar Graphs
    Zhi-Zhong Chen
    Xin He
    Algorithmica , 2004, 38 : 539 - 576
  • [33] Random cubic planar graphs
    Bodirsky, Manuel
    Kang, Mihyun
    Loeffler, Mike
    McDiarmid, Colin
    RANDOM STRUCTURES & ALGORITHMS, 2007, 30 (1-2) : 78 - 94
  • [34] Acyclic edge colorings of planar graphs and seriesparallel graphs
    JianFeng Hou
    JianLiang Wu
    GuiZhen Liu
    Bin Liu
    Science in China Series A: Mathematics, 2009, 52 : 605 - 616
  • [35] Disk embeddings of planar graphs
    Chen, ZZ
    He, X
    ALGORITHMICA, 2004, 38 (04) : 539 - 576
  • [36] KNOTTED PROJECTIONS OF PLANAR GRAPHS
    TANIYAMA, K
    PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 1995, 123 (11) : 3575 - 3579
  • [37] Angles of planar triangular graphs
    DiBattista, G
    Vismara, L
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 1996, 9 (03) : 349 - 359
  • [38] Minimum choosability of planar graphs
    Wang, Huijuan
    Liu, Bin
    Gai, Ling
    Du, Hongwei
    Wu, Jianliang
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2018, 36 (01) : 13 - 22
  • [39] Diameter bounds for planar graphs
    Fulek, Radoslav
    Moric, Filip
    Pritchard, David
    DISCRETE MATHEMATICS, 2011, 311 (05) : 327 - 335
  • [40] Extending Colorings of Planar Graphs
    Lu, Weihua
    Ren, Han
    GRAPHS AND COMBINATORICS, 2019, 35 (05) : 1161 - 1167
12345