English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

The crossing number of a graph $G$, $\mathrm{cr}(G)$, is the minimum numberof edge crossings arising when drawing a graph on a certain surface.Determining $\mathrm{cr}(G)$ is a problem of great importance in Graph Theory.Its maximum variant, i.e. the maximum crossing number, $\mathrm{max-cr}(G)$, isreceiving growing attention. Instead of an optimization problem on the numberof crossings, here we consider the variance of the number of edge crossings,when embedding the vertices of an arbitrary graph uniformly at random in somespace. In his pioneering research, Moon derived this variance on random lineararrangements of complete unipartite and bipartite graphs. Given the need ofefficient algorithms to support this sort of research and given also thegrowing interest of the number of edge crossings in spatial networks, networkswhere vertices are embedded in some space, here we derive an algorithm tocalculate the variance in arbitrary graphs in time $o(nm^2)$ that we transforminto one that runs in time $O(nm)$ by reusing computations. We also derive onefor forests that runs in time $O(n)$. These algorithms work on a wide range ofrandom layouts (not only on Moon's) and are based on novel arithmeticexpressions for the calculation of the variance that we develop from previoustheoretical work. This paves the way for many applications that rely on a fastbut exact calculation of the variance.

Fast calculation of the variance of edge crossings in random arrangements