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:

enter image description here


  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.

  • $\begingroup$ What is the definition of a "vertex move"? $\endgroup$ – j.c. Nov 15 '17 at 23:42
  • $\begingroup$ A "vertex move" means moving a vertex location on the plane. $\endgroup$ – David G. Stork Nov 15 '17 at 23:55
  • $\begingroup$ Shouldn't the right side of Euler's formula be $1+\kappa$? $\endgroup$ – Jan Kyncl Nov 17 '17 at 1:28
  • $\begingroup$ 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. $\endgroup$ – David G. Stork Nov 17 '17 at 1:47

Your Answer

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

Browse other questions tagged or ask your own question.