MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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|cite|improve this answer

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|cite|improve this answer

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.