2
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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.) $\endgroup$ Mar 6 '11 at 18:21
  • 3
    $\begingroup$ Not any. For example K4 $\endgroup$ Mar 6 '11 at 18:22
14
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ only inside of circle $\endgroup$ Mar 6 '11 at 18:45
  • 3
    $\begingroup$ 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: math.sc.edu/~szekely/ejc9.pdf $\endgroup$ Mar 6 '11 at 19:29
3
$\begingroup$
  1. cr(G) - Crossing Number 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 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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.