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

Given a planar graph $G=(V,E)$ with vertices $V$ and edges $E$, call $\bar G = (V,\bar E)$ a non-planar extension of $G$ if $\bar G$ is non-planar and $E \subset \bar E$.

I'm interested in minimal non-planar extensions in the sense that if $\bar G$ is a non-planar extension of $G$, there is no non-planar extension of $G$ that is a subgraph of $\bar G$.

I first wondered whether these minimal extensions could be unique, but this is quickly disproved by the existence of maximally planar (also called triangulated) graphs. I refine this question slightly:

(1) Is the minimal non-planar extension of an arbitrary planar graph unique up to isomorphism?

(2) What if we define minimality as having the smallest number of edges for one of these extensions?

and also:

(3) Do these extensions mean anything interesting for representations of algebraic objects (eg. groups) on them?

share|improve this question
add comment

2 Answers

up vote 6 down vote accepted

(1) and (2) Take the union of a $K_5$ missing an edge and a $K_{3,3}$ missing an edge. This graph has 2 minimal non-planar extensions, which are obviously not isomorphic.

share|improve this answer
add comment

For a connected example, take a path with 6 vertices. Then, $K_{3,3}$ and $K_5$ together with an additional edge sticking out are both minimal non-planar extensions, again obviously not isomorphic.

share|improve this answer
add comment

Your Answer


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.