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:
- What algorithms find the minimum-cost transformations under the two cost functions?
- 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?
- 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.