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?
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. See the 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.
- cr(G) - Crossing Number is minimum number of crossings with which a graph can be drawn.
- If you are using only straight line edges then its called Rectilinear Crossing Number.
- Determining cr(G) is NP-complete.
- Circular crossing minimization is NP-hard. This paper suggests heuristics to minimize number of crossings. This might be the thing you are here for.
- Crossings in circular layout >= Crossings in any general layout
- Rectilinear crossing number >= Crossing number