# Minimum-cost vertex transformations to achieve a planar graph embedding

Consider an undirected planar graph $G = (V,E)$ (not necessarily simply connected) whose current embedding in the plane has edge intersections.

Consider algorithms in which vertexes $v_i$ can be moved in the plane to achieve a planar embedding (no crossing edges).

Consider two component costs of such vertex moves:

• $c_1$: the number of edges traversed by the vertex on a single move
• $c_2 = 1$: the simple count of the vertex move

Likewise consider two total costs for the transformation from the graph to its planar embedding as the sum of the $c_1$s or the sum of the $c_2$s.

Here is an anti-prism graph in a non-planar embedding and a total $c_1$ cost = 4 transformation (vertex moves, in red) leading to a planar embedding:

Questions

1. What algorithms find the minimum-cost transformations under the two cost functions?
2. What are the worst-case and average-case bounds on the costs for achieving planar graphs, for instance characterized by $|V|$ and $|E|$ and random initial embeddings?
3. Under cost $c_1$, are there any graphs where the minimum total cost transformation demands a given vertex be moved more than once?

I have read papers related to these problems (e.g., here), but none quite address the relationship between the different cost functions.

• What is the definition of a "vertex move"? – j.c. Nov 15 '17 at 23:42
• A "vertex move" means moving a vertex location on the plane. – David G. Stork Nov 15 '17 at 23:55
• Shouldn't the right side of Euler's formula be $1+\kappa$? – Jan Kyncl Nov 17 '17 at 1:28
• I had merely copied the formula from a paper (without careful analysis), but realize I don't need that formula for my question, and hence deleted it. – David G. Stork Nov 17 '17 at 1:47