Circle graph visualisation 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.