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.
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.
Circular layouts are a good fit for communications network topologies such as star or ring networks, [1] and for the cyclic parts of metabolic networks. [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. [3]
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 components, [4] clusters of genes in a gene interaction graph, [5] or natural subgroups within a social network. [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. For instance, a circular drawing algorithm of Gansner & Koren (2007) uses edge bundling within the circle, together with some edges that are not bundled, drawn outside the circle. [12]
For circular layouts of regular graphs, 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. [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. This number of crossings is zero only for outerplanar graphs. [13] For other graphs, it may be optimized or reduced separately for each biconnected component of the graph before combining the solutions, as these components may be drawn so that they do not interact. [14] In general, minimizing the number of crossings is NP-complete. [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. After finding an approximate cut, their algorithm arranges the two subgraphs on each side of the cut recursively, without considering the additional crossings formed by the edges that cross the cut. They prove that the number of crossings occuring in the resulting layout, on a graph with vertices, is
where is the optimal number of crossings and 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 , but this was later found to have an erroneous proof. [17] Instead, the best approximation known for the balanced cut problem has , [18] giving this circular layout algorithm an approximation ratio of 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. [19] A circular layout may also be used to maximize the number of crossings. In particular, choosing a random permutation for the vertices causes each possible crossing to occur with probability 1/3, so the expected number 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 with approximation ratio three. [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. [22]
In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices.
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 graphs arising from applications such as social network analysis, cartography, linguistics, and bioinformatics.
In order theory, a Hasse diagram is a type of mathematical diagram used to represent a finite partially ordered set, in the form of a drawing of its transitive reduction. Concretely, for a partially ordered set one represents each element of as a vertex in the plane and draws a line segment or curve that goes upward from one vertex to another vertex whenever covers . These curves may cross each other but must not touch any vertices other than their endpoints. Such a diagram, with labeled vertices, uniquely determines its partial order.
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 more or less equal length and there are as few crossing edges as possible, by assigning forces among the set of edges and the set of nodes, based on their relative positions, and then using these forces either to simulate the motion of the edges and nodes or to minimize their energy.
In graph theory, a book embedding is a generalization of planar embedding of a graph to embeddings into a book, a collection of half-planes all having the same line as their boundary. Usually, the vertices of the graph are required to lie on this boundary line, called the spine, and the edges are required to stay within a single half-plane. The book thickness of a graph is the smallest possible number of half-planes for any book embedding of the graph. Book thickness is also called pagenumber, stacknumber or fixed outerthickness. Book embeddings have also been used to define several other graph invariants including the pagewidth and book crossing number.
In graph theory, a path decomposition of a graph G is, informally, a representation of G as a "thickened" path graph, and the pathwidth of G is a number that measures how much the path was thickened to form G. More formally, a path-decomposition is a sequence of subsets of vertices of G such that the endpoints of each edge appear in one of the subsets and such that each vertex appears in a contiguous subsequence of the subsets, and the pathwidth is one less than the size of the largest set in such a decomposition. Pathwidth is also known as interval thickness, vertex separation number, or node searching number.
In topological graph theory, an embedding of a graph on a surface is a representation of on in which points of are associated with vertices and simple arcs are associated with edges in such a way that:
In graph theory and theoretical computer science, the longest path problem is the problem of finding a simple path of maximum length in a given graph. A path is called simple if it does not have any repeated vertices; the length of a path may either be measured by its number of edges, or by the sum of the weights of its edges. In contrast to the shortest path problem, which can be solved in polynomial time in graphs without negative-weight cycles, the longest path problem is NP-hard and the decision version of the problem, which asks whether a path exists of at least some given length, is NP-complete. This means that the decision problem cannot be solved in polynomial time for arbitrary graphs unless P = NP. Stronger hardness results are also known showing that it is difficult to approximate. However, it has a linear time solution for directed acyclic graphs, which has important applications in finding the critical path in scheduling problems.
In the mathematical discipline of graph theory, a polygon-circle graph is an intersection graph of a set of convex polygons all of whose vertices lie on a common circle. These graphs have also been called spider graphs. This class of graphs was first suggested by Michael Fellows in 1988, motivated by the fact that it is closed under edge contraction and induced subgraph operations.
Layered graph drawing or hierarchical graph drawing is a type of graph drawing in which the vertices of a directed graph are drawn in horizontal rows or layers with the edges generally directed downwards. It is also known as Sugiyama-style graph drawing after Kozo Sugiyama, who first developed this drawing style.
In graph drawing, the angular resolution of a drawing of a graph is the sharpest angle formed by any two edges that meet at a common vertex of the drawing.
In topological graph theory, a 1-planar graph is a graph that can be drawn in the Euclidean plane in such a way that each edge has at most one crossing point, where it crosses a single additional edge. If a 1-planar graph, one of the most natural generalizations of planar graphs, is drawn that way, the drawing is called a 1-plane graph or 1-planar embedding of the graph.
An arc diagram is a style of graph drawing, in which the vertices of a graph are placed along a line in the Euclidean plane, with edges being drawn as semicircles in one or both of the two halfplanes bounded by the line, or as smooth curves formed by sequences of semicircles. In some cases, line segments of the line itself are also allowed as edges, as long as they connect only vertices that are consecutive along the line. Variations of this drawing style in which the semicircles are replaced by convex curves of some other type are also commonly called arc diagrams.
In graph drawing, an upward planar drawing of a directed acyclic graph is an embedding of the graph into the Euclidean plane, in which the edges are represented as non-crossing monotonic upwards curves. That is, the curve representing each edge should have the property that every horizontal line intersects it in at most one point, and no two edges may intersect except at a shared endpoint. In this sense, it is the ideal case for layered graph drawing, a style of graph drawing in which edges are monotonic curves that may cross, but in which crossings are to be minimized.
In the mathematical field of graph theory, planarization is a method of extending graph drawing methods from planar graphs to graphs that are not planar, by embedding the non-planar graphs within a larger planar graph.
In graph drawing, the area used by a drawing is a commonly used way of measuring its quality.
In graph drawing styles that represent the edges of a graph by polylines, it is desirable to minimize the number of bends per edge or the total number of bends in a drawing. Bend minimization is the algorithmic problem of finding a drawing that minimizes these quantities.
Simultaneous embedding is a technique in graph drawing and information visualization for visualizing two or more different graphs on the same or overlapping sets of labeled vertices, while avoiding crossings within both graphs. Crossings between an edge of one graph and an edge of the other graph are allowed.
In the mathematical area of graph theory, a contact graph or tangency graph is a graph whose vertices are represented by geometric objects, and whose edges correspond to two objects touching according to some specified notion. It is similar to the notion of an intersection graph but differs from it in restricting the ways that the underlying objects are allowed to intersect each other.
In geometric graph theory, a penny graph is a contact graph of unit circles. It is formed from a collection of unit circles that do not cross each other, by creating a vertex for each circle and an edge for every pair of tangent circles. The circles can be represented physically by pennies, arranged without overlapping on a flat surface, with a vertex for each penny and an edge for each two pennies that touch.
