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


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