Reconstructing Maximal Planar Graphs - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-18T05:12:57Z http://mathoverflow.net/feeds/question/26467 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/26467/reconstructing-maximal-planar-graphs Reconstructing Maximal Planar Graphs Derrick Stolee 2010-05-30T16:14:14Z 2010-05-30T18:08:31Z <p>Has it been proven that maximal planar graphs are reconstructible? </p> <p>It seems like an easy result, but I am unable to find it in the literature. Classes of planar graphs that I know are reconstructible are: maximal outerplanar (Manvel 1970), maximal minimally non-outerplanar (has a single interior vertex) (Kunni, Annigeri, 1979), and classes where planar isn't the key property: like trees or cacti (Geller, Manvel, 1969).</p> <p>Perhaps this has not been explicitly answered because it was only recently (Bilinski, Kwon, Yu, 2007) when it was proven that planar graphs are recognizable, which is the "hard" part of this result.</p> <p>Bonus question: Are there other classes of planar graphs that are known to be reconstructible?</p> http://mathoverflow.net/questions/26467/reconstructing-maximal-planar-graphs/26477#26477 Answer by Bhalchandra Thatte for Reconstructing Maximal Planar Graphs Bhalchandra Thatte 2010-05-30T18:08:31Z 2010-05-30T18:08:31Z <p>You may want to look at papers by Fiorini and Lauri. I found the following reference, and I believe there is part II that does reconstruction. But I can't locate it in my bib file, and don't have access to MathSciNet at the moment. Fiorini and Lauri have many papers on other classes of planar graphs. Mostly on edge reconstruction, though. Also look at Bondy's survey Graph Reconstructor's Manual (1991).</p> <p>@article {MR615313, AUTHOR = {Fiorini, S. and Lauri, J.}, TITLE = {The reconstruction of maximal planar graphs. {I}. {R}ecognition}, JOURNAL = {J. Combin. Theory Ser. B}, FJOURNAL = {Journal of Combinatorial Theory. Series B}, VOLUME = {30}, YEAR = {1981}, NUMBER = {2}, PAGES = {188--195}, ISSN = {0095-8956}, CODEN = {JCBTB8}, MRCLASS = {05C60 (05C10 05C35)}, MRNUMBER = {MR615313 (82i:05055a)}, MRREVIEWER = {Thomas Andreae}, }</p>