Arc diagram
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
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
However, every planar graph has an arc diagram in which each edge is drawn as a
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
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
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).
- ^ a b 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).
- PMID 25126961.
- PMID 25228051.
References
- Bekos, Michael A.; Kaufmann, Michael; Kobourov, Stephen G.; Symvonis, Antonios (2013), "Smooth orthogonal layouts", ISBN 978-3-642-36762-5.
- Bernhart, Frank R.; .
- 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", S2CID 1169465
- doi:10.1137/0608002.
- Cimikowski, Robert (2002), "Algorithms for the fixed linear crossing number problem", Discrete Applied Mathematics, 122 (1–3): 93–115, MR 1907825.
- Cimikowski, Robert; Mumey, Brendan (2007), "Approximating the fixed linear crossing number", Discrete Applied Mathematics, 155 (17): 2202–2210, 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, PMID 18255588.
- Djidjev, Hristo; Vrt'o, Imrich (2002), "An improved lower bound for crossing numbers", ISBN 978-3-540-43309-5.
- Efrat, Alon; Erten, Cesim; Kobourov, Stephen G. (2007), "Fixed-location circular arc drawing of planar graphs", .
- 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.
- 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, 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, .
- Heer, Jeffrey; Bostock, Michael; Ogievetsky, Vadim (2010), "A tour through the visualization zoo", .
- Kabakçıoğlu, A.; Stella, A. L. (November 2005), "Scale-free network hidden in a collapsing polymer", Physical Review E, 72 (5), 055102(R), S2CID 29977757
- Masuda, Sumio; Nakajima, Kazuo; Kashiwabara, Toshinobu; Fujisawa, Toshio (1990), "Crossing minimization in linear embeddings of graphs", 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, 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.; S2CID 8643133.
- PMID 16591215.
- S2CID 881989.