Meshedness coefficient explained

In graph theory, the meshedness coefficient is a graph invariant of planar graphs that measures the number of bounded faces of the graph, as a fraction of the possible number of faces for other planar graphs with the same number of vertices. It ranges from 0 for trees to 1 for maximal planar graphs.^{[1] [2]}

Definition

The meshedness coefficient is used to compare the general cycle structure of a connected planar graph to two extreme relevant references. In one end, there are trees, planar graphs with no cycle.^[1] The other extreme is represented by maximal planar graphs, planar graphs with the highest possible number of edges and faces for a given number of vertices. The normalized meshedness coefficient is the ratio of available face cycles to the maximum possible number of face cycles in the graph. This ratio is 0 for a tree and 1 for any maximal planar graph.

More generally, it can be shown using the Euler characteristic that all n-vertex planar graphs have at most 2n - 5 bounded faces (not counting the one unbounded face)and that if there are m edges then the number of bounded faces is m - n + 1 (the same as the circuit rank of the graph).Therefore, a normalized meshedness coefficient can be defined as the ratio of these two numbers:

\alpha = (m - n +1)/(2 n -5) . It varies from 0 for trees to 1 for maximal planar graphs.

Applications

The meshedness coefficient can be used to estimate the redundancy of a network. This parameter along with the algebraic connectivity which measures the robustness of the network, may be used to quantify the topological aspect of network resilience in water distribution networks.^[3] It has also been used to characterize the network structure of streets in urban areas.^{[4] [5] [6]}

Limitations

Using the definition of the average degree

\langle k\rangle = 2 m/n , one can see that in the limit of large graphs (number of edges the meshedness tends to\alpha ≈ (\langle k\rangle)/(4) - (1)/(2) Thus, for large graphs, the meshedness does not carry more information than the average degree.

Notes and References

1. Buhl. J.. Gautrais. J.. Sole . R.V.. Kuntz. P.. Valverde. S.. Deneubourg. J.L.. Theraulaz. G.. 2004. Efficiency and robustness in ant networks of galleries. The European Physical Journal B. 42. 1. 123–129. 10.1140/epjb/e2004-00364-9. 2004EPJB...42..123B. 14975826.
2. Buhl. J.. Gautrais. J.. Reeves . N.. Sole . R.V.. Valverde. S.. Kuntz. P.. Theraulaz. G.. 2006. Topological patterns in street networks of self-organized urban settlements. The European Physical Journal B. 49. 4. 513–522. 10.1140/epjb/e2006-00085-1. 2006EPJB...49..513B. 9862922.
3. Yazdani . A.. Jeffrey. P.. 2012. Applying Network Theory to Quantify the Redundancy and Structural Robustness of Water Distribution Systems. Journal of Water Resources Planning and Management. 138. 2. 153–161. 10.1061/(ASCE)WR.1943-5452.0000159.
4. Wang . X. . Jin . Y. . Abdel-Aty . M. . Tremont . P.J. . Chen . X. . 2012 . Macrolevel Model Development for Safety Assessment of Road Network Structures . Transportation Research Record: Journal of the Transportation Research Board . 2280 . 1 . 100–109 . 10.3141/2280-11 . 110263962 . dead . https://archive.today/20141121202721/http://trb.metapress.com/content/N284113734V14P55 . 2014-11-21.
5. Courtat. T.. Gloaguen. C.. Douady . S.. 2011. Mathematics and morphogenesis of cities: A geometrical approach. Phys. Rev. E. 83. 3. 036106. 10.1103/PhysRevE.83.036106. 21517557. 1010.1762. 2011PhRvE..83c6106C. 808585.
6. Rui. Y.. Ban. Y.. Wang . J.. Haas . J.. 2013. Exploring the patterns and evolution of self-organized urban street networks through modeling. The European Physical Journal B. 86. 3. 036106. 10.1140/epjb/e2012-30235-7. 2013EPJB...86...74R. 254118471.