0
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ Not unless you are also deleting edges. A subgraph of a planar graph is obviously planar. $\endgroup$ – saulspatz May 3 '18 at 21:38
  • $\begingroup$ Edges can be deleted as long as there is still a link to the other object. So a--b could become a--c--b by inserting a node in between, etc. So technically the old edge became split into two edges (so I guess that means deletion). That is okay. $\endgroup$ – Lance Pollard May 3 '18 at 21:40
  • $\begingroup$ @LancePollard Still no, the graphs would remain homeomorphic. See Kuratowski's theorem, you cannot remove a $K_{3,3}$ or $K_5$ minor in that way. $\endgroup$ – Michael Biro May 3 '18 at 21:41
2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ How would that graph be planar? All you've done is drawn a dot $F$ on the edge $AB$. $\endgroup$ – Michael Biro May 3 '18 at 21:48
  • $\begingroup$ "then yes, you could turn a non-planar graph into a planar graph." yay, it seems like this would be possible. If you just place a dot on every edge overlap, then you can convert it into planar it seems. But then I'm wondering how to make it into interesting shapes. $\endgroup$ – Lance Pollard May 3 '18 at 21:49
  • $\begingroup$ Subdividing a non-planar graph cannot make it planar. See en.wikipedia.org/wiki/Kuratowski%27s_theorem. Also, deciding if a given graph is planar can be done in linear time (see same link). $\endgroup$ – Manuel Lafond May 4 '18 at 1:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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