Arc diagram

In an arc diagram, the vertices of a graph are arranged along a line in the Euclidean plane. The edges are 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.{{sfnp|Nagel|Duval|2013}}

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 {{harvtxt|Fekete|Wang|Dang|Aris|2003}}, and applied to arc diagrams by {{harvtxt|Pretorius|van Wijk|2007}}.

The use of the phrase "arc diagram" for this kind of drawing follows the use of a similar type of diagram by {{harvtxt|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 at least to the work of {{harvtxt|Saaty|1964}} and {{harvtxt|Nicholson|1968}}, who used arc diagrams to study crossing numbers of graphs.{{harvtxt|Saaty|1964}}; {{harvtxt|Nicholson|1968}}.

Arc diagrams are also called linear embeddings.{{sfnp|Masuda|Nakajima|Kashiwabara|Fujisawa|1990}} In their application to the circuit topology of RNA secondary structure, they are called circuit diagrams.{{sfnp|Mashaghi|van der Veen|2021}}

As {{harvtxt|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.{{sfnp|Nicholson|1968}}

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. This kind of drawing is only possible for the subhamiltonian graphs, a proper subset of the planar graphs.The application of semicircles to edge layout in book embeddings was already made by {{harvtxt|Bernhart|Kainen|1979}}, but the explicit connection of arc diagrams with two-page book embeddings seems to be due to {{harvtxt|Masuda|Nakajima|Kashiwabara|Fujisawa|1990}}. 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.As {{harvtxt|Goldner|Harary|1975}} show, this is the smallest non-Hamiltonian maximal planar graph. The implication that it has no two-page book embedding is stated by {{harvtxt|Bekos|Gronemann|Pupyrev|Raftopoulou|2014}}. Testing whether a given graph has a crossing-free arc diagram of this type (or equivalently, whether it has pagenumber two) is NP-complete.{{sfnp|Chung|Leighton|Rosenberg|1987}}

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.{{sfnp|Giordano|Liotta|Mchedlidze|Symvonis|2007}} 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.{{sfnp|Bekos|Kaufmann|Kobourov|Symvonis|2013}} In a planar graph with $n$ vertices, at most $n/2$ biarcs are needed.{{sfnp|Cardinal|Hoffmann|Kusters|Tóth|2018}}

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.{{sfnp|Masuda|Nakajima|Kashiwabara|Fujisawa|1990}} 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.{{sfnp|Efrat|Erten|Kobourov|2007}} 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).{{sfnp|Cimikowski|Mumey|2007}}

{{harvtxt|Cimikowski|Shope|1996}}, {{harvtxt|Cimikowski|2002}}, and {{harvtxt|He|Sýkora|Vrt'o|2005}} discuss heuristics for finding arc diagrams with few crossings.

For applications in information visualization, {{harvtxt|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.{{sfnp|Heer|Bostock|Ogievetsky|2010}} Arc diagrams were used by {{harvtxt|Brandes|1999}} to visualize the state diagram of a shift register,{{sfnp|Brandes|1999}} by {{harvtxt|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,{{sfnp|Djidjev|Vrt'o|2002}} by {{harvtxt|Byrne|Lavelle|Jones|Smeaton|2007}} to visualize interactions between Bluetooth devices,{{sfnp|Byrne|Lavelle|Jones|Smeaton|2007}} and by {{harvtxt|Owens|Jankun-Kelly|2013}} to visualize the yardage of plays in a game of American football.{{sfnp|Owens|Jankun-Kelly|2013}} Additional applications of this visualization technique are surveyed by {{harvtxt|Nagel|Duval|2013}}.{{sfnp|Nagel|Duval|2013}}

File:Farey diagram horizontal arc 9.svg]]

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.{{sfnp|Gilman|Keen|2002}}

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.{{sfnp|Mashaghi|van Wijk|Tans|2014}}

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.{{sfnp|Mugler|Tans|Mashaghi|2014}}

{{reflist|colwidth=30em}}

{{refbegin|colwidth=30em}}

• {{citation

| last1 = Bekos | first1 = Michael A.

| last2 = Kaufmann | first2 = Michael

| last3 = Kobourov | first3 = Stephen G.

| last4 = Symvonis | first4 = Antonios

| contribution = Smooth orthogonal layouts

| doi = 10.1007/978-3-642-36763-2_14

| pages = 150–161

| publisher = Springer

| series = Lecture Notes in Computer Science

| title = Graph Drawing: 20th International Symposium, GD 2012, Redmond, WA, USA, September 19–21, 2012, Revised Selected Papers

| volume = 7704

| year = 2013| isbn = 978-3-642-36762-5

| doi-access = free

}}.

• {{citation

| last1 = Bekos | first1 = Michael A.

| last2 = Gronemann | first2 = Martin

| last3 = Pupyrev | first3 = Sergey

| last4 = Raftopoulou | first4 = Chrysanthi N.

| editor1-last = Bourbakis | editor1-first = Nikolaos G.

| editor2-last = Tsihrintzis | editor2-first = George A.

| editor3-last = Virvou | editor3-first = Maria

| contribution = Perfect smooth orthogonal drawings

| doi = 10.1109/IISA.2014.6878731

| pages = 76–81

| publisher = {IEEE}

| title = 5th International Conference on Information, Intelligence, Systems and Applications, IISA 2014, Chania, Crete, Greece, July 7–9, 2014

| year = 2014| isbn = 978-1-4799-6171-9

}}

• {{citation|first1=Frank R.|last1=Bernhart|first2=Paul C.|last2=Kainen|author2-link=Paul Chester Kainen|title=The book thickness of a graph|journal=Journal of Combinatorial Theory|series=Series B|volume=27|issue=3|pages=320–331|year=1979|doi=10.1016/0095-8956(79)90021-2|doi-access=free}}.
• {{citation

| last = Brandes | first = Ulrik | author-link = Ulrik Brandes

| contribution = Hunting down Graph B

| doi = 10.1007/3-540-46648-7_42

| pages = 410–415

| publisher = Springer

| series = Lecture Notes in Computer Science

| title = Graph Drawing: 7th International Symposium, GD'99, Štiřín Castle, Czech Republic September 15–19, 1999, Proceedings

| volume = 1731

| year = 1999| isbn = 978-3-540-66904-3

| doi-access = free

}}.

• {{citation

| last1 = Byrne | first1 = Daragh

| last2 = Lavelle | first2 = Barry

| last3 = Jones | first3 = Gareth J. F.

| last4 = Smeaton | first4 = Alan F.

| editor1-last = Ormerod | editor1-first = Thomas C.

| editor2-last = Sas | editor2-first = Corina

| contribution = Visualising Bluetooth interactions: combining the Arc diagram and DocuBurst techniques

| contribution-url = https://doras.dcu.ie/342/1/hci_2007.pdf

| pages = 129–132

| publisher = British Computer Society

| title = 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

| year = 2007}}.

• {{citation

| last1 = Cardinal | first1 = Jean

| last2 = Hoffmann | first2 = Michael

| last3 = Kusters | first3 = Vincent

| last4 = Tóth | first4 = Csaba D.

| last5 = Wettstein | first5 = Manuel

| arxiv = 1611.02541

| doi = 10.1016/j.comgeo.2017.06.001

| journal = Computational Geometry

| mr = 3715053

| pages = 206–225

| title = Arc diagrams, flip distances, and Hamiltonian triangulations

| volume = 68

| year = 2018| s2cid = 1169465

}}

• {{citation

| last1 = Chung | first1 = Fan R. K. | author1-link = Fan Chung

| last2 = Leighton | first2 = Frank Thompson | author2-link = F. Thomson Leighton

| last3 = Rosenberg | first3 = Arnold L. | author3-link = Arnold L. Rosenberg

| doi = 10.1137/0608002

| issue = 1

| journal = SIAM Journal on Algebraic and Discrete Methods

| pages = 33–58

| title = Embedding graphs in books: A layout problem with applications to VLSI design

| url = http://www.math.ucsd.edu/~fan/mypaps/fanpap/fc82embedding.pdf

| volume = 8

| year = 1987}}.

• {{citation

| last = Cimikowski | first = Robert

| doi = 10.1016/S0166-218X(01)00314-6

| issue = 1–3

| journal = Discrete Applied Mathematics

| mr = 1907825

| pages = 93–115

| title = Algorithms for the fixed linear crossing number problem

| volume = 122

| year = 2002| doi-access = free

}}.

• {{citation

| last1 = Cimikowski | first1 = Robert

| last2 = Mumey | first2 = Brendan

| doi = 10.1016/j.dam.2007.05.009

| issue = 17

| journal = Discrete Applied Mathematics

| mr = 2360650

| pages = 2202–2210

| title = Approximating the fixed linear crossing number

| volume = 155

| year = 2007| doi-access = free

}}.

• {{citation

| last1 = Cimikowski | first1 = Robert

| last2 = Shope | first2 = Paul

| doi = 10.1109/72.485670

| issue = 2

| journal = IEEE Transactions on Neural Networks

| pages = 341–345

| title = A neural-network algorithm for a graph layout problem

| volume = 7

| year = 1996| pmid = 18255588

}}.

• {{citation

| last1 = Djidjev | first1 = Hristo

| last2 = Vrt'o | first2 = Imrich

| contribution = An improved lower bound for crossing numbers

| doi = 10.1007/3-540-45848-4_8

| pages = 96–101

| publisher = Springer

| series = Lecture Notes in Computer Science

| title = Graph Drawing: 9th International Symposium, GD 2001, Vienna, Austria, September 23–26, 2001, Revised Papers

| volume = 2265

| year = 2002| isbn = 978-3-540-43309-5

| doi-access = free

}}.

• {{citation

| last1 = Efrat | first1 = Alon

| last2 = Erten | first2 = Cesim

| last3 = Kobourov | first3 = Stephen G.

| doi = 10.7155/jgaa.00140

| issue = 1

| journal = Journal of Graph Algorithms and Applications

| pages = 145–164

| title = Fixed-location circular arc drawing of planar graphs

| volume = 11

| year = 2007| doi-access = free

}}.

• {{citation

| last1 = Fekete | first1 = Jean-Daniel

| last2 = Wang | first2 = David

| last3 = Dang | first3 = Niem

| last4 = Aris | first4 = Aleks

| last5 = Plaisant | first5 = Catherine

| contribution = Overlaying graph links on treemaps

| pages = 82–83

| title = IEEE Symp. on Information Visualization, Poster Compendium

| year = 2003}}.

• {{citation

| last1 = Gilman | first1 = Jane | author1-link = Jane Piore Gilman

| last2 = Keen | first2 = Linda | author2-link = Linda Keen

| contribution = Word sequences and intersection numbers

| contribution-url = http://comet.lehman.cuny.edu/keenl/words.pdf

| doi = 10.1090/conm/311/05455

| mr = 1940172

| pages = 231–249

| publisher = American Mathematical Society | location = Providence, Rhode Island

| series = Contemporary Mathematics

| title = Complex manifolds and hyperbolic geometry (Guanajuato, 2001)

| volume = 311

| year = 2002| isbn = 978-0-8218-2957-8 }}; see Section 2.4, "Farey diagrams and continued fractions"

• {{citation

| last1 = Giordano | first1 = Francesco

| last2 = Liotta | first2 = Giuseppe

| last3 = Mchedlidze | first3 = Tamara

| last4 = Symvonis | first4 = Antonios

| contribution = Computing upward topological book embeddings of upward planar digraphs

| doi = 10.1007/978-3-540-77120-3_17

| pages = 172–183

| publisher = Springer

| series = Lecture Notes in Computer Science

| title = Algorithms and Computation: 18th International Symposium, ISAAC 2007, Sendai, Japan, December 17-19, 2007, Proceedings

| volume = 4835

| year = 2007| isbn = 978-3-540-77118-0

}}.

• {{citation|first1=A.|last1=Goldner|first2=F.|last2=Harary|author2-link=Frank Harary|title=Note on a smallest nonhamiltonian maximal planar graph|journal=Bull. Malaysian Math. Soc.|volume=6|issue=1|year=1975|pages=41–42}}. See also the same journal 6(2):33 (1975) and 8:104-106 (1977). Reference from [http://www.cs.nmsu.edu/fnh/publ.html listing of Harary's publications].
• {{citation

| last1 = He | first1 = Hongmei

| last2 = Sýkora | first2 = Ondrej

| last3 = Vrt'o | first3 = Imrich

| doi = 10.1016/j.endm.2005.06.088

| journal = Electronic Notes in Discrete Mathematics

| pages = 527–534

| title = Crossing Minimisation Heuristics for 2-page Drawings

| volume = 22

| year = 2005| url = https://figshare.com/articles/Crossing_minimisation_Heuristics_for_2-page_drawings/9401915

}}.

• {{citation

| last1 = Heer | first1 = Jeffrey

| last2 = Bostock | first2 = Michael

| last3 = Ogievetsky | first3 = Vadim

| doi = 10.1145/1743546.1743567

| issue = 6

| journal = Communications of the ACM

| pages = 59–67

| title = A tour through the visualization zoo

| volume = 53

| year = 2010| doi-access = free

}}.

• {{citation

| last1 = Kabakçıoğlu | first1 = A.

| last2 = Stella | first2 = A. L.

| arxiv = cond-mat/0409584

| at = 055102(R)

| date = November 2005

| doi = 10.1103/physreve.72.055102

| issue = 5

| journal = Physical Review E

| title = Scale-free network hidden in a collapsing polymer

| volume = 72| pmid = 16383674

| bibcode = 2005PhRvE..72e5102K

| s2cid = 29977757

}}.

• {{citation

| last1 = Mashaghi | first1 = Alireza

| last2 = van der Veen | first2 = Roland

| arxiv = 2109.02391

| date = September 2021

| doi = 10.3390/sym13091751

| issue = 9

| journal = Symmetry

| page = 1751

| publisher = MDPI AG

| title = Polynomial invariant of molecular circuit topology

| volume = 13| doi-access = free

| bibcode = 2021Symm...13.1751M

}}.

• {{citation| doi=10.1016/j.str.2014.06.015 | pmid=25126961 | volume=22 | issue=9 | title=Circuit Topology of Proteins and Nucleic Acids | year=2014 | journal=Structure | pages=1227–1237 | last1 = Mashaghi | first1 = Alireza | last2 = van Wijk | first2 = Roeland J. | last3 = Tans | first3 = Sander J.| doi-access=free }}
• {{citation

| last1 = Masuda | first1 = Sumio

| last2 = Nakajima | first2 = Kazuo

| last3 = Kashiwabara | first3 = Toshinobu

| last4 = Fujisawa | first4 = Toshio

| doi = 10.1109/12.46286

| issue = 1

| journal = IEEE Transactions on Computers

| mr = 1032144

| pages = 124–127

| title = Crossing minimization in linear embeddings of graphs

| volume = 39

| year = 1990}}.

• {{citation

| last1 = Mugler | first1 = Andrew

| last2 = Tans | first2 = Sander J.

| last3 = Mashaghi | first3 = Alireza

| bibcode = 2014PCCP...1622537M

| doi = 10.1039/C4CP03402C

| issue = 41

| journal = Physical Chemistry Chemical Physics

| pages = 22537–22544

| pmid = 25228051

| title = Circuit topology of self-interacting chains: implications for folding and unfolding dynamics

| volume = 16

| year = 2014}}.

• {{citation

| last1 = Nagel | first1 = Till

| last2 = Duval | first2 = Erik

| contribution = A visual survey of arc diagrams

| contribution-url = https://uclab.fh-potsdam.de/wp/wp-content/uploads/2013-a-visual-survey-of-arc-diagrams.pdf

| publisher = IEEE

| title = 2013 VIS Posters

| year = 2013}}

• {{citation

| last = Nicholson | first = T. A. J.

| doi = 10.1049/piee.1968.0004

| journal = Proceedings of the Institution of Electrical Engineers

| mr = 0311416

| pages = 21–26

| title = Permutation procedure for minimising the number of crossings in a network

| volume = 115

| year = 1968}}.

• {{citation

| last1 = Owens | first1 = Sean Gabriel

| last2 = Jankun-Kelly | first2 = T. J.

| contribution = Visualizations for exploration of American football season and play data

| contribution-url = https://workshop.sportvis.com/papers/owens_jankun-kelly_paper.pdf

| publisher = IEEE

| title = 1st IEEE VIS Workshop on Sports Data Visualization

| year = 2013}}

• {{citation

| last1 = Pretorius | first1 = A. J.

| last2 = van Wijk | first2 = J. J. | author2-link = Jack van Wijk

| doi = 10.1109/MCG.2007.121

| pmid = 17913025

| issue = 5

| journal = IEEE Computer Graphics and Applications

| pages = 58–66

| title = Bridging the semantic gap: Visualizing transition graphs with user-defined diagrams

| volume = 27

| year = 2007| s2cid = 8643133

}}.

• {{citation

| last = Saaty | first = Thomas L. | authorlink = Thomas L. Saaty

| journal = Proceedings of the National Academy of Sciences of the United States of America

| mr = 0166772

| pages = 688–690

| title = The minimum number of intersections in complete graphs

| volume = 52

| issue = 3 | year = 1964

| doi=10.1073/pnas.52.3.688| pmc = 300329 | pmid=16591215| bibcode = 1964PNAS...52..688S | doi-access = free }}.

• {{citation

| last = Wattenberg | first = M. | authorlink = Martin M. Wattenberg

| contribution = Arc diagrams: visualizing structure in strings

| doi = 10.1109/INFVIS.2002.1173155

| pages = 110–116

| title = Proc. IEEE Symposium o nInformation Visualization (INFOVIS 2002)

| year = 2002| isbn = 0-7695-1751-X | s2cid = 881989 }}.

{{refend}}

Category:Graph drawing