Arc diagram

Last updated December 08, 2024

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.^[1]

The use of the phrase "arc diagram" for this kind of drawing follows the use of a similar type of diagram by Wattenberg (2002) to visualize the repetition patterns in strings, by using arcs to connect pairs of equal substrings. However, this style of graph drawing is much older than its name, dating back to the work of Saaty (1964) and Nicholson (1968), who used arc diagrams to study crossing numbers of graphs. An older but less frequently used name for arc diagrams is linear embeddings.^[2] More recently, arc diagrams have been used within the framework of circuit topology of knots and tangles, where they are termed as circuit diagrams.^[3]

Heer, Bostock & Ogievetsky (2010) write that arc diagrams "may not convey the overall structure of the graph as effectively as a two-dimensional layout", but that their layout makes it easy to display multivariate data associated with the vertices of the graph. Applications of arc diagrams include the Farey diagram, a visualization of number-theoretic connections between rational numbers, and diagrams representing RNA secondary structure in which the crossings of the diagram represent pseudoknots in the structure.

Planar graphs

As Nicholson (1968) observed, every drawing of a graph in the plane may be deformed into an arc diagram, without changing its number of crossings. In particular, every planar graph has a planar arc diagram. However, this embedding may need to use more than one semicircle for some of its edges.

If a graph is drawn without crossings using an arc diagram in which each edge is a single semicircle, then the drawing is a two-page book embedding, something that is only possible for the subhamiltonian graphs, a proper subset of the planar graphs.^[4] For instance, a maximal planar graph has such an embedding if and only if it contains a Hamiltonian cycle. Therefore, a non-Hamiltonian maximal planar graph such as the Goldner–Harary graph cannot have a planar embedding with one semicircle per edge. Testing whether a given graph has a crossing-free arc diagram of this type (or equivalently, whether it has pagenumber two) is NP-complete.^[5]

However, every planar graph has an arc diagram in which each edge is drawn as a biarc with at most two semicircles. More strongly, every st-planar directed graph (a planar directed acyclic graph with a single source and a single sink, both on the outer face) has an arc diagram in which every edge forms a monotonic curve, with these curves all consistently oriented from one end of the vertex line towards the other.^[6] For undirected planar graphs, one way to construct an arc diagram with at most two semicircles per edge is to subdivide the graph and add extra edges so that the resulting graph has a Hamiltonian cycle (and so that each edge is subdivided at most once), and to use the ordering of the vertices on the Hamiltonian cycle as the ordering along the line.^[7] In a planar graph with $n$ vertices, at most $n/2$ biarcs are needed.^[8]

Minimizing crossings

Because it is NP-complete to test whether a given graph has an arc diagram with one semicircle per edge and no crossings, it is also NP-hard to find an arc diagram of this type that minimizes the number of crossings. This crossing minimization problem remains NP-hard, for non-planar graphs, even if the ordering of the vertices along the line is fixed.^[2] However, in the fixed-ordering case, an embedding without crossings (if one exists) may be found in polynomial time by translating the problem into a 2-satisfiability problem, in which the variables represent the placement of each arc and the constraints prevent crossing arcs from being placed on the same side of the vertex line.^[9] Additionally, in the fixed-ordering case, a crossing-minimizing embedding may be approximated by solving a maximum cut problem in an auxiliary graph that represents the semicircles and their potential crossings (or equivalently, by approximating the MAX2SAT version of the 2-satisfiability instance).^[10]

Cimikowski & Shope (1996), Cimikowski (2002), and He, Sýkora & Vrt'o (2005) discuss heuristics for finding arc diagrams with few crossings.

Clockwise orientation

For drawings of directed graphs, a common convention is to draw each arc in a clockwise direction, so that arcs that are directed from an earlier to a later vertex in the sequence are drawn above the vertex line, and arcs directed from a later to an earlier vertex are drawn below the line. This clockwise orientation convention was developed as part of a different graph drawing style by Fekete et al. (2003), and applied to arc diagrams by Pretorius & van Wijk (2007).

Applications

The Farey diagram of a set of rational numbers is a structure that may be represented geometrically as an arc diagram. In this form it has a vertex for each number, placed on the number line, and a semicircular edge above the line connecting pairs of numbers $p/q$ and $r/s$ (in simplest terms) for which $|ps-rq|=1$ . The semicircles of the diagram may be thought of as lines in the Poincaré half-plane model of the hyperbolic plane, with the vertices placed at infinite points on the boundary line of this model. The Poincaré half-plane model has an infinite point that is not represented as point on the boundary line, the shared endpoint of all vertical rays in the model, and this may be represented by the "fraction" 1/0 (undefined as a number), with the same rule for determining its adjacencies. The Farey diagram of any set of rational numbers is a planar graph, and the Farey diagram of the set of all rational numbers forms a tessellation of the hyperbolic plane by ideal triangles.^[11]

Arc diagrams or circuit diagrams are commonly used in studying folded biopolymers such as proteins and nucleic acids (DNAs, RNAs). Biopolymers are typically represented by their primary monomer sequence along the line of the diagrams, and with arcs above the line representing bonds between monomers (e.g., amino acids in proteins or bases in RNA or DNA) that are adjacent in the physical structure of the polymer despite being nonadjacent in the sequence order. The theoretical framework of circuit topology is then typically applied to extract local and global topological information, which can in turn be related to biological function of the folded molecules.^[12] When arcs do not cross, the arrangement of the two arcs will be either parallel (P) or series (S). When there are crossings, the crossings represent what is often called as X arrangement in circuit topology. The statistics of P, S, and X can be used to learn about folding kinetics of these polymers.^[13]

Arc diagrams were used by Brandes (1999) to visualize the state diagram of a shift register, by Djidjev & Vrt'o (2002) to show that the crossing number of every graph is lower-bounded by a combination of its cutwidth and vertex degrees, by Byrne et al. (2007) to visualize interactions between Bluetooth devices, and by Owens & Jankun-Kelly (2013) to visualize the yardage of plays in a game of American football. Additional applications of this visualization technique are surveyed by Nagel & Duval (2013).

Notes

↑ Nagel & Duval (2013).
1 2 Masuda et al. (1990).
↑ Alireza Mashaghi and Roland van der Veen, Polynomial Invariant of Molecular Circuit Topology Symmetry 13(9), 1751 (2021)
↑ The application of semicircles to edge layout in book embeddings was already made by Bernhart & Kainen (1979), but the explicit connection of arc diagrams with two-page book embeddings seems to be due to Masuda et al. (1990).
↑ Chung, Leighton & Rosenberg (1987).
↑ Giordano et al. (2007).
↑ Bekos et al. (2013).
↑ Cardinal et al. (2018).
↑ Efrat, Erten & Kobourov (2007).
↑ Cimikowski & Mumey (2007).
↑ Gilman & Keen (2002).
↑ Mashaghi, Alireza; van Wijk, Roeland J.; Tans, Sander J. (2014). "Circuit Topology of Proteins and Nucleic Acids". Structure. 22 (9): 1227–1237. doi: 10.1016/j.str.2014.06.015 . PMID 25126961.
↑ Mugler, Andrew; Tans, Sander J.; Mashaghi, Alireza (2014). "Circuit topology of self-interacting chains: implications for folding and unfolding dynamics". Phys. Chem. Chem. Phys. 16 (41): 22537–22544. Bibcode:2014PCCP...1622537M. doi:10.1039/C4CP03402C. PMID 25228051.

Related Research Articles

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph, or a planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.

The Hamiltonian path problem is a topic discussed in the fields of complexity theory and graph theory. It decides if a directed or undirected graph, G, contains a Hamiltonian path, a path that visits every vertex in the graph exactly once. The problem may specify the start and end of the path, in which case the starting vertex s and ending vertex t must be identified.

In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring.

<span class="mw-page-title-main">Hamiltonian path</span> Path in a graph that visits each vertex exactly once

In the mathematical field of graph theory, a Hamiltonian path is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle is a cycle that visits each vertex exactly once. A Hamiltonian path that starts and ends at adjacent vertices can be completed by adding one more edge to form a Hamiltonian cycle, and removing any edge from a Hamiltonian cycle produces a Hamiltonian path. The computational problems of determining whether such paths and cycles exist in graphs are NP-complete; see Hamiltonian path problem for details.

<span class="mw-page-title-main">Graph drawing</span> Visualization of node-link graphs

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.

<span class="mw-page-title-main">Force-directed graph drawing</span> Physical simulation to visualize graphs

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 the mathematical discipline of graph theory, the dual graph of a planar graph $G$ is a graph that has a vertex for each face of $G$ . The dual graph has an edge for each pair of faces in $G$ that are separated from each other by an edge, and a self-loop when the same face appears on both sides of an edge. Thus, each edge $e$ of $G$ has a corresponding dual edge, whose endpoints are the dual vertices corresponding to the faces on either side of $e$ . The definition of the dual depends on the choice of embedding of the graph $G$ , so it is a property of plane graphs rather than planar graphs. For planar graphs generally, there may be multiple dual graphs, depending on the choice of planar embedding of the graph.

In graph theory, a book embedding is a generalization of planar embedding of a graph to embeddings in 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.

<span class="mw-page-title-main">Hypercube graph</span> Graphs formed by a hypercubes edges and vertices

In graph theory, the hypercube graph $Q n$ is the graph formed from the vertices and edges of an $n$ -dimensional hypercube. For instance, the cube graph $Q 3$ is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. $Q n$ has $2 n$ vertices, $2 n - 1 n$ edges, and is a regular graph with $n$ edges touching each vertex.

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 geometric graph theory, a branch of mathematics, a polyhedral graph is the undirected graph formed from the vertices and edges of a convex polyhedron. Alternatively, in purely graph-theoretic terms, the polyhedral graphs are the 3-vertex-connected, planar graphs.

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.

<span class="mw-page-title-main">Angular resolution (graph drawing)</span> Sharpest angle between edges at a vertex

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 graph drawing, a universal point set of order n is a set S of points in the Euclidean plane with the property that every n-vertex planar graph has a straight-line drawing in which the vertices are all placed at points of S.

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 and geometric graph theory, a Tutte embedding or barycentric embedding of a simple, 3-vertex-connected, planar graph is a crossing-free straight-line embedding with the properties that the outer face is a convex polygon and that each interior vertex is at the average of its neighbors' positions. If the outer polygon is fixed, this condition on the interior vertices determines their position uniquely as the solution to a system of linear equations. Solving the equations geometrically produces a planar embedding. Tutte's spring theorem, proven by W. T. Tutte, states that this unique solution is always crossing-free, and more strongly that every face of the resulting planar embedding is convex. It is called the spring theorem because such an embedding can be found as the equilibrium position for a system of springs representing the edges of the graph.

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.

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.

References

Bekos, Michael A.; Kaufmann, Michael; Kobourov, Stephen G.; Symvonis, Antonios (2013), "Smooth orthogonal layouts", Graph Drawing: 20th International Symposium, GD 2012, Redmond, WA, USA, September 19–21, 2012, Revised Selected Papers, Lecture Notes in Computer Science, vol. 7704, Springer, pp. 150–161, doi: 10.1007/978-3-642-36763-2_14 , ISBN 978-3-642-36762-5 .
Bernhart, Frank R.; Kainen, Paul C. (1979), "The book thickness of a graph", Journal of Combinatorial Theory , Series B, 27 (3): 320–331, doi: 10.1016/0095-8956(79)90021-2 .
Brandes, Ulrik (1999), "Hunting down Graph B", Graph Drawing: 7th International Symposium, GD'99, Štiřín Castle, Czech Republic September 15–19, 1999, Proceedings, Lecture Notes in Computer Science, vol. 1731, Springer, pp. 410–415, doi: 10.1007/3-540-46648-7_42 , ISBN 978-3-540-66904-3 .
Byrne, Daragh; Lavelle, Barry; Jones, Gareth J. F.; Smeaton, Alan F. (2007), "Visualising Bluetooth interactions: combining the Arc diagram and DocuBurst techniques" (PDF), in Ormerod, Thomas C.; Sas, Corina (eds.), Proceedings of the 21st British HCI Group Annual Conference on HCI 2007: HCI...but not as we know it - Volume 2, BCS HCI 2007, University of Lancaster, United Kingdom, 3-7 September 2007, British Computer Society, pp. 129–132.
Cardinal, Jean; Hoffmann, Michael; Kusters, Vincent; Tóth, Csaba D.; Wettstein, Manuel (2018), "Arc diagrams, flip distances, and Hamiltonian triangulations", Computational Geometry , 68: 206–225, arXiv: 1611.02541 , doi:10.1016/j.comgeo.2017.06.001, MR 3715053, S2CID 1169465
Chung, Fan R. K.; Leighton, Frank Thompson; Rosenberg, Arnold L. (1987), "Embedding graphs in books: A layout problem with applications to VLSI design" (PDF), SIAM Journal on Algebraic and Discrete Methods, 8 (1): 33–58, doi:10.1137/0608002 .
Cimikowski, Robert (2002), "Algorithms for the fixed linear crossing number problem", Discrete Applied Mathematics, 122 (1–3): 93–115, doi: 10.1016/S0166-218X(01)00314-6 , MR 1907825 .
Cimikowski, Robert; Mumey, Brendan (2007), "Approximating the fixed linear crossing number", Discrete Applied Mathematics, 155 (17): 2202–2210, doi: 10.1016/j.dam.2007.05.009 , MR 2360650 .
Cimikowski, Robert; Shope, Paul (1996), "A neural-network algorithm for a graph layout problem", IEEE Transactions on Neural Networks, 7 (2): 341–345, doi:10.1109/72.485670, PMID 18255588 .
Djidjev, Hristo; Vrt'o, Imrich (2002), "An improved lower bound for crossing numbers", Graph Drawing: 9th International Symposium, GD 2001, Vienna, Austria, September 23–26, 2001, Revised Papers, Lecture Notes in Computer Science, vol. 2265, Springer, pp. 96–101, doi: 10.1007/3-540-45848-4_8 , ISBN 978-3-540-43309-5 .
Efrat, Alon; Erten, Cesim; Kobourov, Stephen G. (2007), "Fixed-location circular arc drawing of planar graphs", Journal of Graph Algorithms and Applications , 11 (1): 145–164, doi: 10.7155/jgaa.00140 .
Fekete, Jean-Daniel; Wang, David; Dang, Niem; Aris, Aleks; Plaisant, Catherine (2003), "Overlaying graph links on treemaps", IEEE Symp. on Information Visualization, Poster Compendium, pp. 82–83.
Gilman, Jane; Keen, Linda (2002), "Word sequences and intersection numbers" (PDF), Complex manifolds and hyperbolic geometry (Guanajuato, 2001), Contemporary Mathematics, vol. 311, Providence, Rhode Island: American Mathematical Society, pp. 231–249, doi:10.1090/conm/311/05455, ISBN 978-0-8218-2957-8, MR 1940172 ; see Section 2.4, "Farey diagrams and continued fractions"
Giordano, Francesco; Liotta, Giuseppe; Mchedlidze, Tamara; Symvonis, Antonios (2007), "Computing upward topological book embeddings of upward planar digraphs", Algorithms and Computation: 18th International Symposium, ISAAC 2007, Sendai, Japan, December 17-19, 2007, Proceedings, Lecture Notes in Computer Science, vol. 4835, Springer, pp. 172–183, doi:10.1007/978-3-540-77120-3_17, ISBN 978-3-540-77118-0 .
He, Hongmei; Sýkora, Ondrej; Vrt'o, Imrich (2005), "Crossing Minimisation Heuristics for 2-page Drawings", Electronic Notes in Discrete Mathematics, 22: 527–534, doi:10.1016/j.endm.2005.06.088 .
Heer, Jeffrey; Bostock, Michael; Ogievetsky, Vadim (2010), "A tour through the visualization zoo", Communications of the ACM , 53 (6): 59–67, doi: 10.1145/1743546.1743567 .
Kabakçıoğlu, A.; Stella, A. L. (November 2005), "Scale-free network hidden in a collapsing polymer", Physical Review E, 72 (5), 055102(R), arXiv: cond-mat/0409584 , Bibcode:2005PhRvE..72e5102K, doi:10.1103/physreve.72.055102, PMID 16383674, S2CID 29977757
Masuda, Sumio; Nakajima, Kazuo; Kashiwabara, Toshinobu; Fujisawa, Toshio (1990), "Crossing minimization in linear embeddings of graphs", IEEE Transactions on Computers , 39 (1): 124–127, doi:10.1109/12.46286, MR 1032144 .
Nagel, Till; Duval, Erik (2013), "A visual survey of arc diagrams" (PDF), 2013 VIS Posters, IEEE
Nicholson, T. A. J. (1968), "Permutation procedure for minimising the number of crossings in a network", Proceedings of the Institution of Electrical Engineers, 115: 21–26, doi:10.1049/piee.1968.0004, MR 0311416 .
Owens, Sean Gabriel; Jankun-Kelly, T. J. (2013), "Visualizations for exploration of American football season and play data" (PDF), 1st IEEE VIS Workshop on Sports Data Visualization, IEEE
Pretorius, A. J.; van Wijk, J. J. (2007), "Bridging the semantic gap: Visualizing transition graphs with user-defined diagrams", IEEE Computer Graphics and Applications, 27 (5): 58–66, doi:10.1109/MCG.2007.121, PMID 17913025, S2CID 8643133 .
Saaty, Thomas L. (1964), "The minimum number of intersections in complete graphs", Proceedings of the National Academy of Sciences of the United States of America , 52 (3): 688–690, Bibcode:1964PNAS...52..688S, doi: 10.1073/pnas.52.3.688 , MR 0166772, PMC 300329 , PMID 16591215 .
Wattenberg, M. (2002), "Arc diagrams: visualizing structure in strings", Proc. IEEE Symposium o nInformation Visualization (INFOVIS 2002), pp. 110–116, doi:10.1109/INFVIS.2002.1173155, ISBN 0-7695-1751-X, S2CID 881989 .

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[FOOTNOTENagelDuval2013-1] Nagel & Duval (2013).

[FOOTNOTEMasudaNakajimaKashiwabaraFujisawa1990-2] 1 2 Masuda et al. (1990).

[3] Alireza Mashaghi and Roland van der Veen, Polynomial Invariant of Molecular Circuit Topology Symmetry 13(9), 1751 (2021)

[4] The application of semicircles to edge layout in book embeddings was already made by Bernhart & Kainen (1979), but the explicit connection of arc diagrams with two-page book embeddings seems to be due to Masuda et al. (1990).

[FOOTNOTEChungLeightonRosenberg1987-5] Chung, Leighton & Rosenberg (1987).

[FOOTNOTEGiordanoLiottaMchedlidzeSymvonis2007-6] Giordano et al. (2007).

[FOOTNOTEBekosKaufmannKobourovSymvonis2013-7] Bekos et al. (2013).

[FOOTNOTECardinalHoffmannKustersTóth2018-8] Cardinal et al. (2018).

[FOOTNOTEEfratErtenKobourov2007-9] Efrat, Erten & Kobourov (2007).

[FOOTNOTECimikowskiMumey2007-10] Cimikowski & Mumey (2007).

[FOOTNOTEGilmanKeen2002-11] Gilman & Keen (2002).

[12] Mashaghi, Alireza; van Wijk, Roeland J.; Tans, Sander J. (2014). "Circuit Topology of Proteins and Nucleic Acids". Structure. 22 (9): 1227–1237. doi: 10.1016/j.str.2014.06.015 . PMID 25126961.

[13] Mugler, Andrew; Tans, Sander J.; Mashaghi, Alireza (2014). "Circuit topology of self-interacting chains: implications for folding and unfolding dynamics". Phys. Chem. Chem. Phys. 16 (41): 22537–22544. Bibcode:2014PCCP...1622537M. doi:10.1039/C4CP03402C. PMID 25228051.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]