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 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.

Browse other questions tagged or ask your own question.