13
$\begingroup$

Given a planar graph, one can embed it in linear time crossing free into an $n \times n$ grid. I am interested whether any efficient algorithms are known to straight line embed a planar graph crossing free into a $n^c \times n^c$ grid, for some small $c$, such that the minimum angle between two edges is maximized?

$\endgroup$
  • $\begingroup$ I assume you are interested in straight line embedding. Otherwise, the question is trivial... $\endgroup$ – Sariel Har-Peled Jan 22 '12 at 0:00
  • $\begingroup$ yes, I am interested in straight line embeddings $\endgroup$ – Peter Jan 22 '12 at 2:08
15
$\begingroup$

I don't think any such algorithm is known. The results I know about maximizing the minimum angle in straight line drawings of planar graphs are:

  1. Every planar graph has a (possibly nonplanar) drawing in which the minimum angle is inversely proportional to the maximum degree. For the main proof idea and some references, see http://11011110.livejournal.com/230133.html

  2. There exist planar graphs of degree d such that the minimum angle in any straight line planar drawing is $O(\sqrt{(\log d)/d^3})$. This result is due to Garg and Tamassia, "Planar drawings and angular resolution: algorithms and bounds", ESA '94. They also show that achieving near-optimal angles with a grid drawing may require a grid of exponential area.

  3. Every planar graph has a planar drawing in which the minimum angle is bounded by a function of its degree. This can be shown using the Koebe-Andreev-Thurston circle packing theorem. For a reference to a slightly stronger version of this result (showing that every planar graph of bounded degree has a planar drawing with a bounded number of edge slopes) see http://11011110.livejournal.com/205447.html

$\endgroup$
  • $\begingroup$ This answer is very interesting, thank you. Do you know if anything is known about the problem where you want to embed a planar graph crossing free into a grid, s.t. the angle between any edge and the x-axis is a multiple of some $\alpha$ and the goal is to chose $\alpha$ as large as possible? $\endgroup$ – Peter Jan 22 '12 at 13:13
  • $\begingroup$ If you don't already know the embedding, it's NP-complete. Specifically, it's hard to determine whether α=π/2 will work. See Garg and Tamassia, "On the computational complexity of upward and rectilinear planarity testing", SIAM J. Comput. 2001. $\endgroup$ – David Eppstein Jan 23 '12 at 1:11

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.