Reappraising the distribution of the number of edge crossings of graphs on a sphere. (3rd August 2020)

• Record Type: Journal Article
• Authors: Alemany-Puig, Lluís; Mora, Mercè; Ferrer-i-Cancho, Ramon
• Is Part Of: Journal of statistical mechanics. (2020:Aug.)
• Publication Date: 2020-08-03
• Subjects: random graphs, networks -- edge crossings; Statistical mechanics -- Periodicals; Mechanics -- Statistical methods -- Periodicals; 530.1305
• DOI: 10.1088/1742-5468/aba0ab
• Languages: English
• ISSNs: 1742-5468

Abstract

Abstract: 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.