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?


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


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.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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