Graph planarization via rewiring

Question

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.

---

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

---

         
          ^{(a) Nonplanar $G$. (b) $5$ rewirings: planar. (c) $3$ rewirings: planar.}

---

Answer 1

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.

Answer 2

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.