Reappraising the distribution of the number of edge crossings of graphs on a sphere. (English) Zbl 1459.05293
Summary: Many real transportation and mobility networks have their vertices placed on the surface of the Earth. In such embeddings, the edges laid on that surface may cross. In his pioneering research, Moon analyzed the distribution of the number of crossings on complete graphs and complete bipartite graphs whose vertices are located uniformly at random on the surface of a sphere assuming that vertex placements are independent from each other. Here we revise his derivation of that variance in the light of recent theoretical developments on the variance of crossings and computer simulations. We show that Moon’s formulae are inaccurate in predicting the true variance and provide exact formulae.
MSC:
| 05C80 | Random graphs (graph-theoretic aspects) |
| 05C62 | Graph representations (geometric and intersection representations, etc.) |
| 60C05 | Combinatorial probability |
References:
| [1] | CGAL Computational geometry algorithms library http://www.cgal.org |
| [2] | Alemany-Puig L and Ferrer-i-Cancho R 2020 Edge crossings in random linear arrangements J. Stat. Mech. 023403 · Zbl 1456.05119 · doi:10.1088/1742-5468/ab6845 |
| [3] | Barthélemy M 2018 Morphogenesis of Spatial Networks (Berlin: Springer) · Zbl 1382.90001 · doi:10.1007/978-3-319-20565-6 |
| [4] | Bollobás B 1998 Modern Graph Theory (Berlin: Springer) · Zbl 0902.05016 · doi:10.1007/978-1-4612-0619-4 |
| [5] | Chen W Y C, Han H S W and Reidys C M 2009 Random k-noncrossing RNA structures Proc. Natl Acad. Sci.106 22061-6 · Zbl 1203.92026 · doi:10.1073/pnas.0907269106 |
| [6] | Esteban J L and Ferrer-i-Cancho R 2015 A correction on Shiloach’s algorithm for minimum linear arrangement of trees SIAM Journal of Computing46 1146-51 · Zbl 1367.05033 · doi:10.1137/15m1046289 |
| [7] | Ferrer-i-Cancho R 2017 Random crossings in dependency trees Glottometrics37 1-12 |
| [8] | Ferrer-i-Cancho R, Gómez-Rodríguez C and Esteban J L 2018 Are crossing dependencies really scarce? Phys. A 493 311-29 · Zbl 1504.05285 · doi:10.1016/j.physa.2017.10.048 |
| [9] | Granville W A, Smith P F and Mikesh J S 1908 Plane and Spherical Trigonometry (Boston: Ginn and Company) |
| [10] | Guimerá R and Amaral L A N 2004 Modeling the world-wide airport network Eur. Phys. J. B 38 381-5 · doi:10.1140/epjb/e2004-00131-0 |
| [11] | Guimerà R, Mossa S, Turtschi A and Amaral L A N 2005 The worldwide air transportation network: Anomalous centrality, community structure, and cities’ global roles Proc. Natl Acad. Sci. USA102 7794-9 · Zbl 1135.90309 · doi:10.1073/pnas.0407994102 |
| [12] | Kübler S, McDonald R and Nivre J 2009 Dependency parsing Synthesis Lectures on Human Language Technologies2 1-127 · doi:10.2200/S00169ED1V01Y200901HLT002 |
| [13] | Li W and Cai X 2004 Statistical analysis of airport network of China Phys. Rev. E 69 046106 · doi:10.1103/physreve.69.046106 |
| [14] | Liu H, Xu C and Liang J 2017 Dependency distance: a new perspective on syntactic patterns in natural languages Physics of Life Reviews21 171-93 · doi:10.1016/j.plrev.2017.03.002 |
| [15] | Waterloo Maple Inc. Maplesoft, a division of Waterloo Maple Inc |
| [16] | Moon J W 1965 On the distribution of crossings in random complete graphs J. Soc. Ind. Appl. Math.13 506-10 · Zbl 0132.40305 · doi:10.1137/0113032 |
| [17] | Moon J W 1977 Erratum: On the distribution of crossings in random complete graphs J. Soc. Ind. Appl. Math.32 706 · Zbl 0356.90022 · doi:10.1137/0132057 |
| [18] | Piazza B L, Ringeisen R D and Stueckle S K 1991 Properties of nonminimum crossings for some classes of graphs Proc. 6th Quadrennial Int. 1988 Kalamazoo Conf. Graph Theory Combin. Appl.vol 2 ed Y Alavi et al (New York: Wiley) 975-89 · Zbl 0840.05020 |
| [19] | Temperley D and Gildea D 2018 Minimizing syntactic dependency lengths: typological/Cognitive universal? Annual Review of Linguistics4 67-80 · doi:10.1146/annurev-linguistics-011817-045617 |
| [20] | Weisstein E W 2003 Chapter Sphere Point Picking 2nd edn (Boca Raton, FL: Chapman & Hall/CRC) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
