Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Circular layout
open-in-new
<h2 id="applications">Applications</h2> <p>Circular layouts are a good fit for communications <a href="/facts/Network_topology/rBYE0kke">network topologies</a> such as <a href="/facts/Star_network/HPQDmFkI">star</a> or <a href="/facts/Ring_network/GDnXYWDv">ring networks</a>,<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a> and for the cyclic parts of <a href="/facts/Metabolic_network/BYx7DDMH">metabolic networks</a>.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> For graphs with a known <a href="/facts/Hamiltonian_cycle/MHjY2xoY">Hamiltonian cycle</a>, a circular layout allows the cycle to be depicted as the circle, and in this way circular layouts form the basis of the <a href="/facts/LCF_notation/JQt8BMR8">LCF notation</a> for Hamiltonian <a href="/facts/Cubic_graph/6M32WUIJ">cubic graphs</a>.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> </p><p>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 <a href="/facts/Biconnected_component/Y4221AkA">biconnected components</a>,<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> clusters of <a href="/facts/Gene/e1swwPY6">genes</a> in a gene interaction graph,<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> or natural subgroups within a <a href="/facts/Social_network/kQg6aEVf">social network</a>.<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> If multiple vertex circles are used in this way, other methods such as <a href="/facts/Force-directed_graph_drawing/CWAwEwXW">force-directed graph drawing</a> may be used to arrange the clusters.<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> </p><p>One advantage of a circular layout in some of these applications, such as <a href="/facts/Bioinformatic/D5x2L8ee">bioinformatics</a> or social network visualization, is its neutrality:<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> 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.<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a> </p> <h2 id="edge-style">Edge style</h2> <p>The edges of the drawing may be depicted as <a href="/facts/Chord_(geometry)/aAyoEdLd">chords</a> of the circle,<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a> as circular arcs<a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a> (possibly perpendicular to the vertex circle, so that the edges model lines of the <a href="/facts/Poincar%25C3%25A9_disk_model/6nCWjbRL">Poincaré disk model</a> of <a href="/facts/Hyperbolic_geometry/DjTMKdgy">hyperbolic geometry</a>), or as other types of curve.<a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a> </p><p>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.<a class="footnote-ref" id="fnref:13" href="#fn:13"><sup>13</sup></a> </p><p>For circular layouts of <a href="/facts/Regular_graph/j9dSoLE6">regular graphs</a>, with edges drawn both inside and outside as <a href="/facts/Arc_(geometry)/xBQ0pTBW">circular arcs</a>, the <a href="/facts/Angle_of_incidence_(optics)/DTaCjhTU">angle of incidence</a> 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 <a href="/facts/Angular_resolution_(graph_drawing)/yeX4mDcP">angular resolution</a> of the drawing.<a class="footnote-ref" id="fnref:14" href="#fn:14"><sup>14</sup></a> </p> <h2 id="number-of-crossings">Number of crossings</h2> <p>Several authors have studied the problem of finding a <a href="/facts/Permutation/JSw9ukmv">permutation</a> of the vertices of a circular layout that minimizes the <a href="/facts/Crossing_number_(graph_theory)/x3Yz6UhF">number of edge crossings</a> when all edges are drawn inside the vertex circle. This number of crossings is zero only for <a href="/facts/Outerplanar_graph/FrAgUpcV">outerplanar graphs</a>.<a class="footnote-ref" id="fnref:15" href="#fn:15"><sup>15</sup></a> For other graphs, it may be optimized or reduced separately for each <a href="/facts/Biconnected_component/Y4221AkA">biconnected component</a> of the graph before combining the solutions, as these components may be drawn so that they do not interact.<a class="footnote-ref" id="fnref:16" href="#fn:16"><sup>16</sup></a> In general, minimizing the number of crossings is <a href="/facts/NP-complete/NFPv56DU">NP-complete</a>.<a class="footnote-ref" id="fnref:17" href="#fn:17"><sup>17</sup></a> </p><p>Shahrokhi et al. (1995) described an <a href="/facts/Approximation_algorithm/BWlf7M32">approximation algorithm</a> based on <a href="/facts/Cut_(graph_theory)/1lKf2IIW">balanced cuts</a> 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 occurring in the resulting layout, on a graph G {\displaystyle G} with n {\displaystyle n} vertices, is O ( ( ρ log n ) 2 ⋅ ( C + ∑ v ∈ V ( G ) deg ( v ) 2 ) ) , {\displaystyle O{\Bigl (}{\bigl (}\rho \log n{\bigr )}^{2}\cdot {\bigl (}C+\sum _{v\in V(G)}\deg(v)^{2}{\bigr )}{\Bigr )},} where C {\displaystyle C} is the optimal number of crossings and ρ {\displaystyle \rho } is the approximation ratio of the balanced cut algorithm used by this layout method.<a class="footnote-ref" id="fnref:18" href="#fn:18"><sup>18</sup></a> Their work cites a paper by <a href="/facts/Fan_Chung/amGEVrj5">Fan Chung</a> and <a href="/facts/Shing-Tung_Yau/qIQclz7g">Shing-Tung Yau</a> from 1994 that claimed ρ = O ( 1 ) {\displaystyle \rho =O(1)} , but this was later found to have an erroneous proof.<a class="footnote-ref" id="fnref:19" href="#fn:19"><sup>19</sup></a> Instead, the best approximation known for the balanced cut problem has ρ = O ( log n ) {\displaystyle \rho =O({\sqrt {\log n}})} ,<a class="footnote-ref" id="fnref:20" href="#fn:20"><sup>20</sup></a> giving this circular layout algorithm an <a href="/facts/Approximation_ratio/BWlf7M32">approximation ratio</a> of O ( log 3 n ) {\displaystyle O(\log ^{3}n)} on graphs that have a large number of crossings relative to their <a href="/facts/Degree_(graph_theory)/LnFFpI8v">vertex degrees</a>. </p><p>Heuristic methods for reducing the crossing complexity have also been devised, based e.g. on a careful vertex insertion order and on <a href="/facts/Local_search_(optimization)/G1D2aHBz">local optimization</a>.<a class="footnote-ref" id="fnref:21" href="#fn:21"><sup>21</sup></a> A circular layout may also be used to maximize the number of crossings. In particular, choosing a <a href="/facts/Random_permutation/zJMPNXlz">random permutation</a> for the vertices causes each possible crossing to occur with probability 1/3, so the <a href="/facts/Expected_value/1XV0JKL8">expected number</a> of crossings is within a factor of three of the maximum number of crossings among all possible layouts. <a href="/facts/Derandomization/Fngl1zgk">Derandomizing</a> this method gives a <a href="/facts/Deterministic_algorithm/v8x4wz35">deterministic</a> <a href="/facts/Approximation_algorithm/BWlf7M32">approximation algorithm</a> with <a href="/facts/Approximation_ratio/BWlf7M32">approximation ratio</a> three.<a class="footnote-ref" id="fnref:22" href="#fn:22"><sup>22</sup></a> </p> <h2 id="other-optimization-criteria">Other optimization criteria</h2> <p>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 <a href="/facts/Cutwidth/Tov7sEyX">cutwidth</a> (the maximum number of edges that connects one arc of the circle to the opposite arc) have also been considered,<a class="footnote-ref" id="fnref:23" href="#fn:23"><sup>23</sup></a> but many of these problems are NP-complete.<a class="footnote-ref" id="fnref:24" href="#fn:24"><sup>24</sup></a> </p> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Chord_diagram_(information_visualization)/EwDLnAEy">Chord diagram (information visualization)</a>, a closely related concept in information visualization</li> <li><a href="/facts/Planarity/cvlgDlrU">Planarity</a>, a puzzle in which a player must move vertices to untangle a drawing of a <a href="/facts/Planar_graph/plREagr9">planar graph</a>, starting from a randomized circular layout</li></ul> <h2 id="external-links">External links</h2> <ul><li><a href="https://graphviz.org/docs/layouts/circo/">Circular layout engine of Graphviz</a></li></ul> <h2 id="notes">Notes</h2> <ul><li><a href="/facts/Sanjeev_Arora/W3C8BLQI">Arora, Sanjeev</a>; <a href="/facts/Satish_Rao/3hjYM8kS">Rao, Satish</a>; <a href="/facts/Umesh_Vazirani/ej4NSg84">Vazirani, Umesh</a> (2009), <a href="https://people.eecs.berkeley.edu/~vazirani/pubs/arvfull.pdf">"Expander flows, geometric embeddings and graph partitioning"</a> (PDF), <i><a href="/facts/Journal_of_the_ACM/qkIF9LLS">Journal of the ACM</a></i>, 56 (2): A5:1–A5:37, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F1502793.1502794">10.1145/1502793.1502794</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=2535878">2535878</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:52151977">52151977</a></li> <li>Baur, Michael; <a href="/facts/Ulrik_Brandes/LUPCvR6c">Brandes, Ulrik</a> (2005), "Crossing reduction in circular layouts", in van Leeuwen, Jan (ed.), <a href="https://publikationen.bibliothek.kit.edu/1000001244/1027"><i>Graph-Theoretic Concepts in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004, Revised Papers</i></a>, <a href="/facts/Lecture_Notes_in_Computer_Science/1UeA77BC">Lecture Notes in Computer Science</a>, vol. 3353, Springer, pp. 332–343, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F978-3-540-30559-0_28">10.1007/978-3-540-30559-0_28</a>.</li> <li>Becker, Moritz Y.; Rojas, Isabel (2001), "A graph layout algorithm for drawing metabolic pathways", <i>Bioinformatics</i>, 17 (5): 461–467, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1093%2Fbioinformatics%2F17.5.461">10.1093/bioinformatics/17.5.461</a>, <a href="/facts/PMID_(identifier)/JlHAvMHt">PMID</a> <a href="https://pubmed.ncbi.nlm.nih.gov/11331241">11331241</a>.</li> <li>Dehkordi, Hooman Reisi; Nguyen, Quan; <a href="/facts/Peter_Eades/QkuQtjxA">Eades, Peter</a>; <a href="/facts/Seok-Hee_Hong/jxkIexkY">Hong, Seok-Hee</a> (2013), "Circular graph drawings with large crossing angles", <i>Algorithms and Computation: 7th International Workshop, WALCOM 2013, Kharagpur, India, February 14-16, 2013, Proceedings</i>, Lecture Notes in Computer Science, vol. 7748, Springer, pp. 298–309, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F978-3-642-36065-7_28">10.1007/978-3-642-36065-7_28</a>.</li> <li>Doğrusöz, Uğur; Belviranli, M.; Dilek, A. (2012), "CiSE: A circular spring embedder layout algorithm", <i>IEEE Transactions on Visualization and Computer Graphics</i>, 19 (6): 953–966, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1109%2FTVCG.2012.178">10.1109/TVCG.2012.178</a>, <a href="/facts/Hdl_(identifier)/rdebSxmC">hdl</a>:<a href="https://hdl.handle.net/11693%2F21006">11693/21006</a>, <a href="/facts/PMID_(identifier)/JlHAvMHt">PMID</a> <a href="https://pubmed.ncbi.nlm.nih.gov/23559509">23559509</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:14365664">14365664</a>.</li> <li>Doğrusöz, Uğur; Madden, Brendan; Madden, Patrick (1997), "Circular layout in the Graph Layout toolkit", <i><a href="/facts/International_Symposium_on_Graph_Drawing/KNNSXw64">Graph Drawing: Symposium on Graph Drawing, GD '96, Berkeley, California, USA, September 18–20, 1996, Proceedings</a></i>, Lecture Notes in Computer Science, vol. 1190, Springer, pp. 92–100, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F3-540-62495-3_40">10.1007/3-540-62495-3_40</a>.</li> <li>Duncan, Christian A.; <a href="/facts/David_Eppstein/hIjTU6nC">Eppstein, David</a>; <a href="/facts/Michael_T._Goodrich/YatXTwPL">Goodrich, Michael T.</a>; Kobourov, Stephen G.; Nöllenburg, Martin (2012), "Lombardi drawings of graphs", <i><a href="/facts/Journal_of_Graph_Algorithms_and_Applications/7oUrnKzR">Journal of Graph Algorithms and Applications</a></i>, 16 (1): 85–108, <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/1009.0579">1009.0579</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.7155%2Fjgaa.00251">10.7155/jgaa.00251</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:5000926">5000926</a>.</li> <li>Gansner, Emden R.; Koren, Yehuda (2007), <i><a href="/facts/International_Symposium_on_Graph_Drawing/KNNSXw64">Graph Drawing: 14th International Symposium, GD 2006, Karlsruhe, Germany, September 18-20, 2006, Revised Papers</a></i>, Lecture Notes in Computer Science, vol. 4372, Springer, pp. 386–398, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F978-3-540-70904-6_37">10.1007/978-3-540-70904-6_37</a>.</li> <li>He, H.; Sýkora, Ondrej (2004), "New circular drawing algorithms", <a href="https://dspace.lboro.ac.uk/2134/2386"><i>Proceedings of the Workshop on Information Technologies – Applications and Theory (ITAT), Slovakia, September 15-19</i></a>.</li> <li>Huang, Weidong; <a href="/facts/Seok-Hee_Hong/jxkIexkY">Hong, Seok-Hee</a>; <a href="/facts/Peter_Eades/QkuQtjxA">Eades, Peter</a> (2007), "Effects of sociogram drawing conventions and edge crossings in social network visualization", <i><a href="/facts/Journal_of_Graph_Algorithms_and_Applications/7oUrnKzR">Journal of Graph Algorithms and Applications</a></i>, 11 (2): 397–429, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.7155%2Fjgaa.00152">10.7155/jgaa.00152</a>.</li> <li>Iragne, Florian; Nikolski, Macha; Mathieu, Bertrand; Auber, David; Sherman, David (2005), "ProViz: protein interaction visualization and exploration", <i><a href="/facts/Bioinformatics_(journal)/QDgdhR0u">Bioinformatics</a></i>, 21 (2): 272–274, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1093%2Fbioinformatics%2Fbth494">10.1093/bioinformatics/bth494</a>, <a href="/facts/PMID_(identifier)/JlHAvMHt">PMID</a> <a href="https://pubmed.ncbi.nlm.nih.gov/15347570">15347570</a>.</li> <li>Krebs, Valdis (1996), <a href="http://www.orgnet.com/Release1.0-0296.pdf">"Visualizing human networks"</a> (PDF), <i>Release 1.0: Esther Dyson's Monthly Report</i>, 2–96.</li> <li>Mäkinen, Erkki (1988), "On circular layouts", <i>International Journal of Computer Mathematics</i>, 24 (1): 29–37, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1080%2F00207168808803629">10.1080/00207168808803629</a>.</li> <li>Masuda, S.; Kashiwabara, T.; Nakajima, K.; Fujisawa, T. (1987), "On the NP-completeness of a computer network layout problem", <i><a href="/facts/International_Symposium_on_Circuits_and_Systems/WKqCAhzC">Proceedings of the IEEE International Symposium on Circuits and Systems</a></i>, pp. 292–295. As cited by Baur & Brandes (2005).</li> <li>Nguyen, Quan; <a href="/facts/Peter_Eades/QkuQtjxA">Eades, Peter</a>; <a href="/facts/Seok-Hee_Hong/jxkIexkY">Hong, Seok-Hee</a>; Huang, Weidong (2011), "Large crossing angles in circular layouts", <i><a href="/facts/International_Symposium_on_Graph_Drawing/KNNSXw64">Graph Drawing: 18th International Symposium, GD 2010, Konstanz, Germany, September 21-24, 2010, Revised Selected Papers</a></i>, Lecture Notes in Computer Science, vol. 6502, Springer, pp. 397–399, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F978-3-642-18469-7_40">10.1007/978-3-642-18469-7_40</a>.</li> <li><a href="/facts/Toma%25C5%25BE_Pisanski/cVNoaUGH">Pisanski, Tomaž</a>; <a href="/facts/Brigitte_Servatius/F9ezlN4l">Servatius, Brigitte</a> (2013), "2.3.2 Cubic graphs and LCF notation", <a href="https://books.google.com/books?id=bnh2zkuTZr4C&pg=PA32"><i>Configurations from a Graphical Viewpoint</i></a>, Springer, p. 32, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 9780817683641.</li> <li>Shahrokhi, Farhad; Sýkora, Ondrej; Székely, László A.; Vrt'o, Imrich (1995), "Book embeddings and crossing numbers", <i>Graph-Theoretic Concepts in Computer Science: 20th International Workshop, WG '94, Herrsching, Germany, June 16–18, 1994, Proceedings</i>, Lecture Notes in Computer Science, vol. 903, Springer, pp. 256–268, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F3-540-59071-4_53">10.1007/3-540-59071-4_53</a>.</li> <li><a href="/facts/David_Shmoys/v3hDFWn1">Shmoys, David B.</a> (1997), <a href="https://people.orie.cornell.edu/shmoys/pdf/multicut.pdf">"Cut problems and their application to divide-and-conquer"</a> (PDF), in <a href="/facts/Dorit_Hochbaum/oTG3BBDt">Hochbaum, Dorit</a> (ed.), <i>Approximation Algorithms for NP-hard Problems</i>, PWS Publishing, pp. 192–235</li> <li>Six, Janet M.; Tollis, Ioannis G. (1999a), "Circular drawings of biconnected graphs", <i>Algorithm Engineering and Experimentation: International Workshop ALENEX'99, Baltimore, MD, USA, January 15–16, 1999, Selected Papers</i>, Lecture Notes in Computer Science, vol. 1619, Springer, pp. 57–73, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F3-540-48518-X_4">10.1007/3-540-48518-X_4</a>.</li> <li>Six, Janet M.; Tollis, Ioannis G. (1999b), "A framework for circular drawings of networks", <i><a href="/facts/International_Symposium_on_Graph_Drawing/KNNSXw64">Graph Drawing: 7th International Symposium, GD'99, Štiřín Castle, Czech Republic, September 15–19, 1999, Proceedings</a></i>, Lecture Notes in Computer Science, vol. 1731, Springer, pp. 107–116, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F3-540-46648-7_11">10.1007/3-540-46648-7_11</a>.</li> <li>Symeonidis, Alkiviadis; Tollis, Ioannis G. (2004), "Visualization of biological information with circular drawings", <i>Biological and Medical Data Analysis: 5th International Symposium, ISBMDA 2004, Barcelona, Spain, November 18-19, 2004, Proceedings</i>, Lecture Notes in Computer Science, vol. 3337, Springer, pp. 468–478, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F978-3-540-30547-7_47">10.1007/978-3-540-30547-7_47</a>.</li> <li>Verbitsky, Oleg (2008), "On the obfuscation complexity of planar graphs", <i><a href="/facts/Theoretical_Computer_Science_(journal)/Apbc0PDL">Theoretical Computer Science</a></i>, 396 (1–3): 294–300, <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/0705.3748">0705.3748</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2Fj.tcs.2008.02.032">10.1016/j.tcs.2008.02.032</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=2412266">2412266</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:5948167">5948167</a>.</li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Doğrusöz, Madden & Madden (1997). - Doğrusöz, Uğur; Madden, Brendan; Madden, Patrick (1997), "Circular layout in the Graph Layout toolkit", Graph Drawing: Symposium on Graph Drawing, GD '96, Berkeley, California, USA, September 18–20, 1996, Proceedings, Lecture Notes in Computer Science, vol. 1190, Springer, pp. 92–100, doi:10.1007/3-540-62495-3_40 <a href="https://doi.org/10.1007%2F3-540-62495-3_40" target="_blank">https://doi.org/10.1007%2F3-540-62495-3_40</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Becker & Rojas (2001). - Becker, Moritz Y.; Rojas, Isabel (2001), "A graph layout algorithm for drawing metabolic pathways", Bioinformatics, 17 (5): 461–467, doi:10.1093/bioinformatics/17.5.461, PMID 11331241 <a href="https://doi.org/10.1093%2Fbioinformatics%2F17.5.461" target="_blank">https://doi.org/10.1093%2Fbioinformatics%2F17.5.461</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Pisanski & Servatius (2013). - Pisanski, Tomaž; Servatius, Brigitte (2013), "2.3.2 Cubic graphs and LCF notation", Configurations from a Graphical Viewpoint, Springer, p. 32, ISBN 9780817683641 <a href="https://books.google.com/books?id=bnh2zkuTZr4C&pg=PA32" target="_blank">https://books.google.com/books?id=bnh2zkuTZr4C&pg=PA32</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Doğrusöz, Madden & Madden (1997); Six & Tollis (1999b). - Doğrusöz, Uğur; Madden, Brendan; Madden, Patrick (1997), "Circular layout in the Graph Layout toolkit", Graph Drawing: Symposium on Graph Drawing, GD '96, Berkeley, California, USA, September 18–20, 1996, Proceedings, Lecture Notes in Computer Science, vol. 1190, Springer, pp. 92–100, doi:10.1007/3-540-62495-3_40 <a href="https://doi.org/10.1007%2F3-540-62495-3_40" target="_blank">https://doi.org/10.1007%2F3-540-62495-3_40</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Symeonidis & Tollis (2004). - Symeonidis, Alkiviadis; Tollis, Ioannis G. (2004), "Visualization of biological information with circular drawings", Biological and Medical Data Analysis: 5th International Symposium, ISBMDA 2004, Barcelona, Spain, November 18-19, 2004, Proceedings, Lecture Notes in Computer Science, vol. 3337, Springer, pp. 468–478, doi:10.1007/978-3-540-30547-7_47 <a href="https://doi.org/10.1007%2F978-3-540-30547-7_47" target="_blank">https://doi.org/10.1007%2F978-3-540-30547-7_47</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Krebs (1996). - Krebs, Valdis (1996), "Visualizing human networks" (PDF), Release 1.0: Esther Dyson's Monthly Report, 2–96 <a href="http://www.orgnet.com/Release1.0-0296.pdf" target="_blank">http://www.orgnet.com/Release1.0-0296.pdf</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Doğrusöz, Belviranli & Dilek (2012). - Doğrusöz, Uğur; Belviranli, M.; Dilek, A. (2012), "CiSE: A circular spring embedder layout algorithm", IEEE Transactions on Visualization and Computer Graphics, 19 (6): 953–966, doi:10.1109/TVCG.2012.178, hdl:11693/21006, PMID 23559509, S2CID 14365664 <a href="https://doi.org/10.1109%2FTVCG.2012.178" target="_blank">https://doi.org/10.1109%2FTVCG.2012.178</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>Iragne et al. (2005). - Iragne, Florian; Nikolski, Macha; Mathieu, Bertrand; Auber, David; Sherman, David (2005), "ProViz: protein interaction visualization and exploration", Bioinformatics, 21 (2): 272–274, doi:10.1093/bioinformatics/bth494, PMID 15347570 <a href="https://doi.org/10.1093%2Fbioinformatics%2Fbth494" target="_blank">https://doi.org/10.1093%2Fbioinformatics%2Fbth494</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>Huang, Hong & Eades (2007). - Huang, Weidong; Hong, Seok-Hee; Eades, Peter (2007), "Effects of sociogram drawing conventions and edge crossings in social network visualization", Journal of Graph Algorithms and Applications, 11 (2): 397–429, doi:10.7155/jgaa.00152 <a href="https://doi.org/10.7155%2Fjgaa.00152" target="_blank">https://doi.org/10.7155%2Fjgaa.00152</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>Six & Tollis (1999a). - Six, Janet M.; Tollis, Ioannis G. (1999a), "Circular drawings of biconnected graphs", Algorithm Engineering and Experimentation: International Workshop ALENEX'99, Baltimore, MD, USA, January 15–16, 1999, Selected Papers, Lecture Notes in Computer Science, vol. 1619, Springer, pp. 57–73, doi:10.1007/3-540-48518-X_4 <a href="https://doi.org/10.1007%2F3-540-48518-X_4" target="_blank">https://doi.org/10.1007%2F3-540-48518-X_4</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> <li id="fn:11"><p>Duncan et al. (2012). - Duncan, Christian A.; Eppstein, David; Goodrich, Michael T.; Kobourov, Stephen G.; Nöllenburg, Martin (2012), "Lombardi drawings of graphs", Journal of Graph Algorithms and Applications, 16 (1): 85–108, arXiv:1009.0579, doi:10.7155/jgaa.00251, S2CID 5000926 <a href="https://arxiv.org/abs/1009.0579" target="_blank">https://arxiv.org/abs/1009.0579</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li> <li id="fn:12"><p>Gansner & Koren (2007). - Gansner, Emden R.; Koren, Yehuda (2007), Graph Drawing: 14th International Symposium, GD 2006, Karlsruhe, Germany, September 18-20, 2006, Revised Papers, Lecture Notes in Computer Science, vol. 4372, Springer, pp. 386–398, doi:10.1007/978-3-540-70904-6_37 <a href="https://doi.org/10.1007%2F978-3-540-70904-6_37" target="_blank">https://doi.org/10.1007%2F978-3-540-70904-6_37</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li> <li id="fn:13"><p>Gansner & Koren (2007). - Gansner, Emden R.; Koren, Yehuda (2007), Graph Drawing: 14th International Symposium, GD 2006, Karlsruhe, Germany, September 18-20, 2006, Revised Papers, Lecture Notes in Computer Science, vol. 4372, Springer, pp. 386–398, doi:10.1007/978-3-540-70904-6_37 <a href="https://doi.org/10.1007%2F978-3-540-70904-6_37" target="_blank">https://doi.org/10.1007%2F978-3-540-70904-6_37</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></p></li> <li id="fn:14"><p>Duncan et al. (2012). - Duncan, Christian A.; Eppstein, David; Goodrich, Michael T.; Kobourov, Stephen G.; Nöllenburg, Martin (2012), "Lombardi drawings of graphs", Journal of Graph Algorithms and Applications, 16 (1): 85–108, arXiv:1009.0579, doi:10.7155/jgaa.00251, S2CID 5000926 <a href="https://arxiv.org/abs/1009.0579" target="_blank">https://arxiv.org/abs/1009.0579</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></p></li> <li id="fn:15"><p>Six & Tollis (1999a); Baur & Brandes (2005). - Six, Janet M.; Tollis, Ioannis G. (1999a), "Circular drawings of biconnected graphs", Algorithm Engineering and Experimentation: International Workshop ALENEX'99, Baltimore, MD, USA, January 15–16, 1999, Selected Papers, Lecture Notes in Computer Science, vol. 1619, Springer, pp. 57–73, doi:10.1007/3-540-48518-X_4 <a href="https://doi.org/10.1007%2F3-540-48518-X_4" target="_blank">https://doi.org/10.1007%2F3-540-48518-X_4</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></p></li> <li id="fn:16"><p>Baur & Brandes (2005). - Baur, Michael; Brandes, Ulrik (2005), "Crossing reduction in circular layouts", in van Leeuwen, Jan (ed.), Graph-Theoretic Concepts in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004, Revised Papers, Lecture Notes in Computer Science, vol. 3353, Springer, pp. 332–343, doi:10.1007/978-3-540-30559-0_28 <a href="https://publikationen.bibliothek.kit.edu/1000001244/1027" target="_blank">https://publikationen.bibliothek.kit.edu/1000001244/1027</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></p></li> <li id="fn:17"><p>Masuda et al. (1987). - Masuda, S.; Kashiwabara, T.; Nakajima, K.; Fujisawa, T. (1987), "On the NP-completeness of a computer network layout problem", Proceedings of the IEEE International Symposium on Circuits and Systems, pp. 292–295 <a href="#fnref:17" class="footnote-back-ref">↩</a></p></li> <li id="fn:18"><p>Shahrokhi et al. (1995). - Shahrokhi, Farhad; Sýkora, Ondrej; Székely, László A.; Vrt'o, Imrich (1995), "Book embeddings and crossing numbers", Graph-Theoretic Concepts in Computer Science: 20th International Workshop, WG '94, Herrsching, Germany, June 16–18, 1994, Proceedings, Lecture Notes in Computer Science, vol. 903, Springer, pp. 256–268, doi:10.1007/3-540-59071-4_53 <a href="https://doi.org/10.1007%2F3-540-59071-4_53" target="_blank">https://doi.org/10.1007%2F3-540-59071-4_53</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></p></li> <li id="fn:19"><p>Shmoys (1997). - Shmoys, David B. (1997), "Cut problems and their application to divide-and-conquer" (PDF), in Hochbaum, Dorit (ed.), Approximation Algorithms for NP-hard Problems, PWS Publishing, pp. 192–235 <a href="https://people.orie.cornell.edu/shmoys/pdf/multicut.pdf" target="_blank">https://people.orie.cornell.edu/shmoys/pdf/multicut.pdf</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></p></li> <li id="fn:20"><p>Arora, Rao & Vazirani (2009). - Arora, Sanjeev; Rao, Satish; Vazirani, Umesh (2009), "Expander flows, geometric embeddings and graph partitioning" (PDF), Journal of the ACM, 56 (2): A5:1–A5:37, doi:10.1145/1502793.1502794, MR 2535878, S2CID 52151977 <a href="https://people.eecs.berkeley.edu/~vazirani/pubs/arvfull.pdf" target="_blank">https://people.eecs.berkeley.edu/~vazirani/pubs/arvfull.pdf</a> <a href="#fnref:20" class="footnote-back-ref">↩</a></p></li> <li id="fn:21"><p>Mäkinen (1988); Doğrusöz, Madden & Madden (1997); Six & Tollis (1999a); He & Sýkora (2004); Baur & Brandes (2005). - Mäkinen, Erkki (1988), "On circular layouts", International Journal of Computer Mathematics, 24 (1): 29–37, doi:10.1080/00207168808803629 <a href="https://doi.org/10.1080%2F00207168808803629" target="_blank">https://doi.org/10.1080%2F00207168808803629</a> <a href="#fnref:21" class="footnote-back-ref">↩</a></p></li> <li id="fn:22"><p>Verbitsky (2008). - Verbitsky, Oleg (2008), "On the obfuscation complexity of planar graphs", Theoretical Computer Science, 396 (1–3): 294–300, arXiv:0705.3748, doi:10.1016/j.tcs.2008.02.032, MR 2412266, S2CID 5948167 <a href="https://arxiv.org/abs/0705.3748" target="_blank">https://arxiv.org/abs/0705.3748</a> <a href="#fnref:22" class="footnote-back-ref">↩</a></p></li> <li id="fn:23"><p>Mäkinen (1988); Gansner & Koren (2007); Nguyen et al. (2011); Dehkordi et al. (2013). - Mäkinen, Erkki (1988), "On circular layouts", International Journal of Computer Mathematics, 24 (1): 29–37, doi:10.1080/00207168808803629 <a href="https://doi.org/10.1080%2F00207168808803629" target="_blank">https://doi.org/10.1080%2F00207168808803629</a> <a href="#fnref:23" class="footnote-back-ref">↩</a></p></li> <li id="fn:24"><p>Mäkinen (1988). - Mäkinen, Erkki (1988), "On circular layouts", International Journal of Computer Mathematics, 24 (1): 29–37, doi:10.1080/00207168808803629 <a href="https://doi.org/10.1080%2F00207168808803629" target="_blank">https://doi.org/10.1080%2F00207168808803629</a> <a href="#fnref:24" class="footnote-back-ref">↩</a></p></li> </ol>