2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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