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

<ol>
<li><p>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 <a href="http://11011110.livejournal.com/230133.html">http://11011110.livejournal.com/230133.html</a></p></li>
<li><p>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.</p></li>
<li><p>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 <a href="http://11011110.livejournal.com/205447.html">http://11011110.livejournal.com/205447.html</a></p></li>
</ol>

CC BY-SA 3.0
2012-01-22T13:13:46.363Z
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
CC BY-SA 3.0
2012-01-23T01:11:18.207Z
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
CC BY-SA 4.0
2024-10-11T15:47:38.160Z
I am very interested in the references you linked in 1 and 3 but the links seem broken - could you please provide the paper title and author?
beanstalk
CC BY-SA 4.0
2024-10-11T16:52:13.313Z
To answer part of my own question, I believe the reference for 3 is "Drawing planar graphs of bounded degree with few slopes" by Balázs Keszegh, János Pach, and Dömötör Pálvölgyi. https://arxiv.org/abs/1009.1315
beanstalk
CC BY-SA 3.0
2012-01-22T00:14:58.140Z
2012-01-22T00:14:58.140Z
David Eppstein
<p>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?</p>

CC BY-SA 3.0
2012-01-22T00:00:35.633Z
I assume you are interested in straight line embedding. Otherwise, the question is trivial...
Sariel Har-Peled
CC BY-SA 3.0
2012-01-22T02:08:37.810Z
yes, I am interested in straight line embeddings
Peter
<reference-request><graph-theory><graph-drawing>
Graph embedding which maximizes minimum angle
Peter
# Graph embedding which maximizes minimum angle

(Asked by: username_0 on 2012-01-21)

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?

**Tags:** reference-request, graph-theory, graph-drawing

> **Comments:**
> **username_1**: I assume you are interested in straight line embedding. Otherwise, the question is trivial...  
> **username_0**: yes, I am interested in straight line embeddings  

---

## 1 answers

### Answer by username_2 on 2012-01-22. Score: 16 | Accepted 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>

> **Comments:**
> **username_0**: 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?  
> **username_2**: 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.  
> **username_3**: I am very interested in the references you linked in 1 and 3 but the links seem broken - could you please provide the paper title and author?  
> **username_3**: To answer part of my own question, I believe the reference for 3 is "Drawing planar graphs of bounded degree with few slopes" by Balázs Keszegh, János Pach, and Dömötör Pálvölgyi. https://arxiv.org/abs/1009.1315  

---

