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

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