2
$\begingroup$

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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
6
$\begingroup$

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

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .