Circular layout
In graph drawing, a circular layout is a style of drawing that places the vertices of a graph on a circle, often evenly spaced so that they form the vertices of a regular polygon.
[2] For graphs with a known Hamiltonian cycle, a circular layout allows the cycle to be depicted as the circle, and in this way circular layouts form the basis of the LCF notation for Hamiltonian cubic graphs.
[6] If multiple vertex circles are used in this way, other methods such as force-directed graph drawing may be used to arrange the clusters.
[7] One advantage of a circular layout in some of these applications, such as bioinformatics or social network visualization, is its neutrality:[8] by placing all vertices at equal distances from each other and from the center of the drawing, none is given a privileged position, countering the tendency of viewers to perceive more centrally located nodes as being more important.
[9] The edges of the drawing may be depicted as chords of the circle,[10] as circular arcs[11] (possibly perpendicular to the vertex circle, so that the edges model lines of the Poincaré disk model of hyperbolic geometry), or as other types of curve.
[12] The visual distinction between the inside and the outside of the vertex circle in a circular layout may be used to separate two different styles of edge drawing.
[11] Several authors have studied the problem of finding a permutation of the vertices of a circular layout that minimizes the number of edge crossings when all edges are drawn inside the vertex circle.
[15] Shahrokhi et al. (1995) described an approximation algorithm based on balanced cuts or edge separators, subsets of few edges whose removal disconnects the given graph into two subgraphs with approximately equal numbers of vertices.
They prove that the number of crossings occurring in the resulting layout, on a graph
is the approximation ratio of the balanced cut algorithm used by this layout method.
[16] Their work cites a paper by Fan Chung and Shing-Tung Yau from 1994 that claimed
on graphs that have a large number of crossings relative to their vertex degrees.
Heuristic methods for reducing the crossing complexity have also been devised, based e.g. on a careful vertex insertion order and on local optimization.
[20] Along with crossings, circular versions of problems of optimizing the lengths of edges in a circular layout, the angular resolution of the crossings, or the cutwidth (the maximum number of edges that connects one arc of the circle to the opposite arc) have also been considered,[21] but many of these problems are NP-complete.
