# Graph embedding which maximizes minimum angle

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?

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

## 1 Answer

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

• 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? – Peter Jan 22 '12 at 13:13
• 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. – David Eppstein Jan 23 '12 at 1:11