<ol>
<li><a href="http://mathworld.wolfram.com/GraphCrossingNumber.html" rel="nofollow">cr(G) - Crossing Number</a> is minimum number of crossings with which a graph can be drawn.</li>
<li>If you are using only straight line edges then its called Rectilinear Crossing Number.</li>
<li>Determining cr(G) is NP-complete.</li>
<li>Circular crossing minimization is NP-hard. <a href="http://mathworld.wolfram.com/GraphCrossingNumber.html" rel="nofollow"><strong>This paper</strong></a> suggests heuristics to minimize number of crossings. <em>This might be the thing you are here for.</em></li>
<li>Crossings in circular layout >= Crossings in any general layout</li>
<li>Rectilinear crossing number >= Crossing number</li>
</ol>

CC BY-SA 2.5
2011-03-06T19:00:49.250Z
2011-03-06T19:00:49.250Z
Pratik Deoghare
<p>If the edges are permitted to be laid both inside and outside the circle, then it is called the 2-page graphs; if edges can only be laid inside the circle, it is the 1-page graphs, which is also know as the <a href="http://en.wikipedia.org/wiki/Outerplanar_graph" rel="nofollow">outerplanar graphs</a>. See the <a href="http://en.wikipedia.org/wiki/Book_embedding" rel="nofollow">book embedding</a> entry in Wikipedia for more information.</p>

<p>By your comment, I guess the term you're searching for is outerplanar, since the complete graph on 4 vertices is 2-page. Outerplanar graphs can be recognized in linear time; see </p>

<blockquote>
  <p>Linear algorithms to recognize outerplanar and maximal outerplanar graphs, S.L. Mitchell, Information Processing Letters, 1979.</p>
</blockquote>

CC BY-SA 2.5
2011-03-06T18:45:22.650Z
only inside of circle
Eugene Gluhotorenko
CC BY-SA 2.5
2011-03-06T19:29:33.577Z
Right. so outerplanarity is the precise characterization of graphs that can be drawn as you desire without crossings, and so you're looking for drawings that minimize the outerplanar crossing number. This paper might be useful: http://www.math.sc.edu/~szekely/ejc9.pdf
Suresh Venkat
CC BY-SA 2.5
2011-03-06T18:41:03.573Z
2011-03-06T18:41:03.573Z
Hsien-Chih Chang 張顯之
<p>I have a graph. I need visualise it with nodes arranged in a circle. How can I know whether it is possible arrange the nodes on a circle so that there no edges intersect in the visualised graph?</p>

CC BY-SA 2.5
2011-03-06T18:21:02.773Z
Certainly, if the graph is non-planar, this is not possible. On the other hand, I think any planar graph can be visualized on a circle. (But I didn't think about this thoroughly.)
Sadeq Dousti
CC BY-SA 2.5
2011-03-06T18:22:35.580Z
Not any. For example K4
Eugene Gluhotorenko
<graph-theory><co.combinatorics>
Circle graph visualisation
Eugene Gluhotorenko
# Circle graph visualisation

(Asked by: username_0 on 2011-03-06)

I have a graph. I need visualise it with nodes arranged in a circle. How can I know whether it is possible arrange the nodes on a circle so that there no edges intersect in the visualised graph?

**Tags:** graph-theory, co.combinatorics

> **Comments:**
> **username_1**: Certainly, if the graph is non-planar, this is not possible. On the other hand, I think any planar graph can be visualized on a circle. (But I didn't think about this thoroughly.)  
> **username_0**: Not any. For example K4  

---

## 2 answers

### Answer by username_3 on 2011-03-06. Score: 14 | Accepted answer

If the edges are permitted to be laid both inside and outside the circle, then it is called the 2-page graphs; if edges can only be laid inside the circle, it is the 1-page graphs, which is also know as the [outerplanar graphs](http://en.wikipedia.org/wiki/Outerplanar_graph). See the [book embedding](http://en.wikipedia.org/wiki/Book_embedding) entry in Wikipedia for more information.

By your comment, I guess the term you're searching for is outerplanar, since the complete graph on 4 vertices is 2-page. Outerplanar graphs can be recognized in linear time; see

> Linear algorithms to recognize outerplanar and maximal outerplanar graphs, S.L. Mitchell, Information Processing Letters, 1979.

> **Comments:**
> **username_0**: only inside of circle  
> **username_4**: Right. so outerplanarity is the precise characterization of graphs that can be drawn as you desire without crossings, and so you're looking for drawings that minimize the outerplanar crossing number. This paper might be useful: http://www.math.sc.edu/~szekely/ejc9.pdf  

---

### Answer by username_2 on 2011-03-06. Score: 3

1. [cr(G) - Crossing Number](http://mathworld.wolfram.com/GraphCrossingNumber.html) is minimum number of crossings with which a graph can be drawn.
2. If you are using only straight line edges then its called Rectilinear Crossing Number.
3. Determining cr(G) is NP-complete.
4. Circular crossing minimization is NP-hard. [**This paper**](http://mathworld.wolfram.com/GraphCrossingNumber.html) suggests heuristics to minimize number of crossings. *This might be the thing you are here for.*
5. Crossings in circular layout >= Crossings in any general layout
6. Rectilinear crossing number >= Crossing number


---

