Obtaining a planar graph from a non-planar graph through vertex addition

1.1k Views Asked by At

Wondering if it is possible to construct a planar graph from any non-planar graph by adding vertices (or splitting edges arbitrarily), and if so, if there is any technique to it. Wondering if there is any study of how to generate specific planar shapes and such out of arbitrary graphs. If not, why not. I'm thinking along the lines of just doing this: adding points wherever the edges overlap. But then how to create shapes. Not sure if there is any math done on this already.

enter image description here $\to$ enter image description here

1

There are 1 best solutions below

3
On BEST ANSWER

It depends on what you mean by "adding vertices."

The usual meaning is to place a new point which is then connected by zero or more edges to existing points. In that case, it is almost obvious that you cannot get a planar graph from a non-planar graph, because there will be a subgraph of the new graph (namely the original non-planar graph) that cannot be expressed in a plane.

But if "adding a point" can mean adding a point along an edge, breaking that edge and requiring the corresponding two edges to connect to the new point (along perhaps with other edges) then yes, you could turn a non-planar graph into a planar graph.

For example, take a 5-clique, which is non-planar. Choose an edge, wlog edge $AB$. Remove that edge and replace it with two edges connecting a sixth point $F$ (so that the new graph has $AF$ and $FB$ in place of $AB$). This new graph is planar.

I believe determining whether a given graph is planar, knowing only its matrix of edges, is a hard problem.


I believe I need to explain my example in more detail:

In a plane, picture geometrically points $$\{ A = (0,1); B = (0, -1); C = (1,0); D = (-1,0); E = (0,0) \}$$ and edges depicted by lines $AC$, $AD$, $AE$, $BC$, $BD$, $BE$, $CE$, $DE$, plus an edge between $A$ and $B$ drawn as an arc within the same plane, and one last edge between $C$ and $D$ (making this $K_5$) drawn as a curve going slightly out of the plane, going from $C$ around the outside of $A$, just over the $AB$ arc, and coming back down near $D$.

Now break (as the OP is trying to allow in his problem) arc $AB$ into arcs $AF$ and $FB$, both still using the same drawn curve (and in the plane). Then push arc $CD$ dwon into the plane such that it would cross arc $AB$ at $F$, and break up $CD$ into $CF$ and $FD$. The resulting graph of six vertices is now planar (indeed, the planar edge set has been exhibited by construction). It is not, or course a 6-clique, nor does it contain $K_5$ as a subgraph, but this does meet the OP's desire for "flattening" a graph.