Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Has it been proven that maximal planar graphs are reconstructible?

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).

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.

Bonus question: Are there other classes of planar graphs that are known to be reconstructible?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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).

@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}, }

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.