9
$\begingroup$

Let $G$ be a nonplanar graph (undirected) of $n$ nodes and $e$ edges, with $e \le 3n-6$. Define a rewiring move as replacing edge $(a,b)$ with edge $(a,c)$. The result must be a simple graph (no loops, no multiple edges). So after each rewiring, the number of vertices and edges is the same: $n$ and $e$.

I would like to find the fewest number of rewirings that converts $G$ to a planar graph. An example is shown below.


          Rewire
          (a) $e=11 \le 3n-6=12$. (b) Edge $(1,3)$ rewired to $(1,6)$. (c) Planar embedding.
My main question is: Has this notion been studied before, and if so, under what terminology? If it hasn't been studied, I would be interested in a proof that every such nonplanar graph can be rendered planar via rewirings, or a counterexample.

Added. Here is another example, of what Gerhard calls a balloon graph. The five rewirings (b) $$(1,3), \; (1,4), \; (1,5) \to (1,7), \; (1,8), \; (1,9)\\ (5,2), \; (5,3) \to (5,7), \; (5,8) $$ obviously reach planarity, but just the three rewirings (c) $$(1,3), \; (1,4) \to (1,7), \; (1,8) \\ (5,3) \to (5,7) $$ less obviously result in a planar graph. I don't think two rewirings suffice.


          HexBalloon
          (a) Nonplanar $G$. (b) $5$ rewirings: planar. (c) $3$ rewirings: planar.


$\endgroup$
  • 2
    $\begingroup$ Say that $G\sim H$ if $G$ can be transformed to $H$ by rewirings. Is it true that $G\sim H$ iff $G$ and $H$ have the same numbers of vertices and edges? $\endgroup$ – Jalex Stark May 8 '18 at 13:19
  • $\begingroup$ @JalexStark: Yes, that is my intention. I should have specified simple graph. Will correct. $\endgroup$ – Joseph O'Rourke May 8 '18 at 15:21
  • $\begingroup$ @JosephO'Rourke Would the minimal number of rewirings be the same as the number of edges that need to be removed (instead of rewired)? $\endgroup$ – Moritz Firsching May 8 '18 at 15:32
  • 1
    $\begingroup$ @MoritzFirsching Not obviously, if the graph triangulates some surface. $\endgroup$ – Igor Rivin May 8 '18 at 15:34
  • $\begingroup$ @Jalex, I believe your statement holds, as it takes at most two allowed rewirings to remove edge (a,b) and install edge (c,d). Gerhard "See Answer For Proof Sketch" Paseman, 2018.05.08. $\endgroup$ – Gerhard Paseman May 8 '18 at 19:05
2
$\begingroup$

Indeed, for every pair (n,m) in your domain (m+6 at most 3n) there is a planar graph on n vertices with m edges: take a path of n-2 vertices, and add an edge from each vertex to each of two additional vertices u and v. Add the edge u,v, and now take away enough edges from this planar graph to get down to m edges. Any of your non planar graphs can be rewired to one of these selected planar graphs this way.

(As an aside, it might be of interest to rewire while preserving degree sequence. I suggest searching for that as well.)

Using the large example above, take w to be one of the n-2 vertices, and rewire all the path edges to turn w into the center of a star with all the other (n-3) path vertices connected to w. We now have degree of u,v,and w each at n-1, and all the remaining path vertices have degree 3. I conjecture that this example will need almost if not exactly a third of its edges rewired to become planar, and that it will be a significant challenge to find a graph needing proportionately more rewiring.

On the other hand (assuming the graph is connected, as having more components probably makes the rewiring easier) one can choose a spanning tree of the original graph and preserve that and just rewire other edges. Thus at least 1/3 of the edges can be kept. One can extend this slightly to have a spanning bonsai, which is like a spanning tree but with additional edges that do not cross, and thus preserve a little more of the graph. I am not sure how to find a large spanning bonsai in a connected graph.

In the above, I am assuming that I can freely remove and replace edges at will. J.C. gently reminds me that a sequence is involved where the start and final edge of a move share a vertex. I outline an argument that shows every replacement removal can be implemented by a few of these rewirings.

So we want to remove an edge (a,b) and install edge (c,d). If the four named vertices are really three, this is just a rewiring. If one of the four pairs ac ad bc bd does not exist, this is accomplished by two rewirings. If disaster befalls us and those four edges are taken, we rewire one of them to cd, and then rewire ab to the removed edge. I think this is about as clean a proof sketch as one can get. So I reassert my previous claim that all graphs can be rewired to one of the graphs at the start of this post. I leave the formalization to others.

Gerhard "Graph Theory, Meet Topological Gardening" Paseman, 2018.05.08.

$\endgroup$
  • $\begingroup$ Could you give a little more detail on the rewiring process you have in mind (or a sketch of a proof that one exists)? $\endgroup$ – j.c. May 8 '18 at 16:29
  • $\begingroup$ One might start a bonsai by picking a vertex with high degree, creating branches from that, and then grafting on original edges between selected pairs of branches. Gerhard "Looks Like A Spider Web" Paseman, 2018.05.08. $\endgroup$ – Gerhard Paseman May 8 '18 at 16:29
  • $\begingroup$ J.c. I am not sure what detail would help. If you could quote part of the answer that puzzles you, I could expand on that. Gerhard "It's As Clear As Dirt" Paseman, 2018.05.08. $\endgroup$ – Gerhard Paseman May 8 '18 at 16:31
  • $\begingroup$ Note that I am talking about number of edges preserved. The rewiring sequence may be twice as long and tedious. I have not remarked about minimizing the sequence length yet. Gerhard "Edge Count Is Lower Bound" Paseman, 2018.05.08. $\endgroup$ – Gerhard Paseman May 8 '18 at 16:34
  • $\begingroup$ I was hoping you could justify this statement: "Any of your non planar graphs can be rewired to one of these selected planar graphs this way." In particular it would be interesting to see (along the lines of Jalex Stark's comment above) whether your method could answer the following question: Let $G_{m,n}$ be the graph whose vertex set is the set of graphs with $m$ edges and $n$ vertices and which has an edge between every pair of graphs connected by a rewiring move. For which values $(m,n)$ it is true that $G_{m,n}$ is connected? $\endgroup$ – j.c. May 8 '18 at 16:40
1
$\begingroup$

Here is a refutation of a conjecture from the other answer. Make a balloon graph: Take a small clique of k vertices, and add a long path to it so the result is connected, has n vertices, and has n-k edges outside the clique, but the total number of edges is at most 3n-6. In order to make this planar, edges have to be removed from the clique and added to the path, leaving something like fewer than 3k vertices in the clique, and so moving k(k/2 -3) edges which can be made close to 2n for a judicious choice of n and k. So I refine the statement to say that any rewireable graph can be made planar in at most 4n rewiring moves, and that there are examples where (4- epsilon)n such moves are necessary.

Backpedal 2018.05.08. GRP

I retract the part of the statement where I say that there are examples requiring almost 4n rewiring moves. I still believe examples exist with close to 2n edges needing to be moved, but it looks like most of these edges can be relocated with a single rewiring move. Take a graph with m edges, and color a bonsai of at least n edges green, and imagine the rest (almost 2n many) as colored red and needing to be moved. Even if the red edges are clumped together inside a k-clique, each can be pivoted out to one of about (n-k) many choices to make a graph planar, and so a lot of fixing can be done with one rewiring per edge. Although 4n and (2 - epsilon) n seem like good upper and lower bounds, I now suspect the upper bound can be improved substantially.

End Backpedal 2018.05.08. GRP

Gerhard "Balloon Sounds Better Than Mace" Paseman, 2018.05.08.

$\endgroup$
  • $\begingroup$ The balloon example may be doable in 2n wirings or fewer. However, once you string several balloons together, I can see getting up to near 4n rewirings needed. Again I will let someone with more ambition work out the details. Gerhard "Leaves Argument Up In Air" Paseman, 2018.05.08. $\endgroup$ – Gerhard Paseman May 8 '18 at 19:29
  • $\begingroup$ Hmm. Now I see something else. Guess I'd better think more. Gerhard "What Is That Hissing Sound?" Paseman, 2018.05.08. $\endgroup$ – Gerhard Paseman May 8 '18 at 20:16

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.