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?



Minimal Non-planar Extensions of a Graph
(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. 


