![Barabasi Albert model](https://upload.wikimedia.org/wikipedia/commons/4/48/Barabasi_Albert_model.gif)
In
graph drawing
Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graph (discrete mathematics), graphs arising from applications such a ...
, a circular layout is a style of drawing that places the
vertices of a
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
on a
circle
A circle is a shape consisting of all points in a plane that are at a given distance from a given point, the centre. Equivalently, it is the curve traced out by a point that moves in a plane so that its distance from a given point is con ...
, often evenly spaced so that they form the vertices of a
regular polygon
In Euclidean geometry, a regular polygon is a polygon that is Equiangular polygon, direct equiangular (all angles are equal in measure) and Equilateral polygon, equilateral (all sides have the same length). Regular polygons may be either convex p ...
.
Applications
Circular layouts are a good fit for communications
network topologies such as
star
A star is an astronomical object comprising a luminous spheroid of plasma (physics), plasma held together by its gravity. The List of nearest stars and brown dwarfs, nearest star to Earth is the Sun. Many other stars are visible to the naked ...
or
ring networks, and for the cyclic parts of
metabolic network
A metabolic network is the complete set of metabolic and physical processes that determine the physiological and biochemical properties of a cell. As such, these networks comprise the chemical reactions of metabolism, the metabolic pathways, as w ...
s. For graphs with a known
Hamiltonian cycle
In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex ...
, 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
In the mathematical field of graph theory, LCF notation or LCF code is a notation devised by Joshua Lederberg, and extended by H. S. M. Coxeter and Robert Frucht, for the representation of cubic graphs that contain a Hamiltonian cycle. The cycle ...
for Hamiltonian
cubic graph
In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs.
A bicubic graph is a cubic bi ...
s.
A circular layout may be used on its own for an entire graph drawing, but it also may be used as the layout for smaller clusters of vertices within a larger graph drawing, such as its
biconnected component
In graph theory, a biconnected component (sometimes known as a 2-connected component) is a maximal biconnected subgraph. Any connected graph decomposes into a tree of biconnected components called the block-cut tree of the graph. The blocks a ...
s, clusters of
gene
In biology, the word gene (from , ; "...Wilhelm Johannsen coined the word gene to describe the Mendelian units of heredity..." meaning ''generation'' or ''birth'' or ''gender'') can have several different meanings. The Mendelian gene is a ba ...
s in a gene interaction graph, or natural subgroups within a
social network
A social network is a social structure made up of a set of social actors (such as individuals or organizations), sets of dyadic ties, and other social interactions between actors. The social network perspective provides a set of methods for ...
. If multiple vertex circles are used in this way, other methods such as
force-directed graph drawing
Force-directed graph drawing algorithms are a class of algorithms for drawing graphs in an aesthetically-pleasing way. Their purpose is to position the nodes of a graph in two-dimensional or three-dimensional space so that all the edges are of m ...
may be used to arrange the clusters.
One advantage of a circular layout in some of these applications, such as
bioinformatic
Bioinformatics () is an interdisciplinary field that develops methods and software tools for understanding biological data, in particular when the data sets are large and complex. As an interdisciplinary field of science, bioinformatics combine ...
s or social network visualization, is its neutrality: 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.
Edge style
The edges of the drawing may be depicted as
chords
Chord may refer to:
* Chord (music), an aggregate of musical pitches sounded simultaneously
** Guitar chord a chord played on a guitar, which has a particular tuning
* Chord (geometry), a line segment joining two points on a curve
* Chord ( ...
of the circle, as circular arcs
(possibly perpendicular to the vertex circle, so that the edges model lines of the
Poincaré disk model of
hyperbolic geometry
In mathematics, hyperbolic geometry (also called Lobachevskian geometry or Bolyai–Lobachevskian geometry) is a non-Euclidean geometry. The parallel postulate of Euclidean geometry is replaced with:
:For any given line ''R'' and point ''P ...
), or as other types of curve.
[.]
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. For instance, a circular drawing algorithm of uses edge bundling within the circle, together with some edges that are not bundled, drawn outside the circle.
For circular layouts of
regular graph
In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegr ...
s, with edges drawn both inside and outside as
circular arcs, the
angle of incidence of one of these arcs with the vertex circle is the same at both ends of the arc, a property that simplifies the optimization of the
angular resolution of the drawing.
[.]
Number of crossings
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. This number of crossings is zero only for
outerplanar graph
In graph theory, an outerplanar graph is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing.
Outerplanar graphs may be characterized (analogously to Wagner's theorem for planar graphs) by the two fo ...
s. For other graphs, it may be optimized or reduced separately for each
biconnected component
In graph theory, a biconnected component (sometimes known as a 2-connected component) is a maximal biconnected subgraph. Any connected graph decomposes into a tree of biconnected components called the block-cut tree of the graph. The blocks a ...
of the graph before combining the solutions, as these components may be drawn so that they do not interact.
In general, minimizing the number of crossings is
NP-complete
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...
, but may be approximated with an approximation ratio of ''O''(log
2 ''n'') where ''n'' is the number of vertices. Heuristic methods for reducing the crossing complexity have also been devised, based e.g. on a careful vertex insertion order and on
local optimization.
A circular layout may also be used to maximize the number of crossings. In particular, choosing a
random permutation
A random permutation is a random ordering of a set of objects, that is, a permutation-valued random variable. The use of random permutations is often fundamental to fields that use randomized algorithms such as coding theory, cryptography, and sim ...
for the vertices causes each possible crossing to occur with probability 1/3, so the
expected number
In probability theory, the expected value (also called expectation, expectancy, mathematical expectation, mean, average, or first moment) is a generalization of the weighted average. Informally, the expected value is the arithmetic mean of a ...
of crossings is within a factor of three of the maximum number of crossings among all possible layouts.
Derandomizing this method gives a
deterministic approximation algorithm
In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solu ...
with
approximation ratio
An approximation is anything that is intentionally similar but not exactly equal to something else.
Etymology and usage
The word ''approximation'' is derived from Latin ''approximatus'', from ''proximus'' meaning ''very near'' and the prefix ' ...
three.
Other optimization criteria
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, but many of these problems are NP-complete.
[.]
See also
*
Chord diagram (information visualization)
A chord diagram is a graphical method of displaying the inter-relationships between data in a matrix. The data are arranged radially around a circle with the relationships between the data points typically drawn as arcs connecting the data.
The ...
, a closely related concept in information visualization
*
Planarity
Planarity is a puzzle computer game by John Tantalo, based on a concept by Mary Radcliffe at Western Michigan University.
The name comes from the concept of planar graphs in graph theory; these are graphs that can be embedded in the Euclidean pla ...
, a puzzle in which a player must move vertices to untangle a drawing of a
planar graph, starting from a randomized circular layout
External links
Circular layout engine of Graphviz
Notes
References
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*. As cited by .
*.
*.
*.
*.
*.
*.
*.
{{refend
Graph drawing
Circles