Meshedness coefficient

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 ={\frac {m-n+1}{2n-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 =2m/n$ , one can see that in the limit of large graphs (number of edges $n\gg 1$ ) the meshedness tends to

\alpha \approx {\frac {\langle k\rangle }{4}}-{\frac {1}{2}}

Thus, for large graphs, the meshedness does not carry more information than the average degree.

References

^ ^a ^b 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. Bibcode:2004EPJB...42..123B. doi:10.1140/epjb/e2004-00364-9. S2CID 14975826.
^ 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. Bibcode:2006EPJB...49..513B. doi:10.1140/epjb/e2006-00085-1. S2CID 9862922.
^ 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. doi:10.1061/(ASCE)WR.1943-5452.0000159.
^ 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. doi:10.3141/2280-11. S2CID 110263962. Archived from the original on 2014-11-21.
^ Courtat, T.; Gloaguen, C.; Douady, S. (2011). "Mathematics and morphogenesis of cities: A geometrical approach". Phys. Rev. E. 83 (3): 036106. arXiv:1010.1762. Bibcode:2011PhRvE..83c6106C. doi:10.1103/PhysRevE.83.036106. PMID 21517557. S2CID 808585.
^ 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. Bibcode:2013EPJB...86...74R. doi:10.1140/epjb/e2012-30235-7. S2CID 254118471.

[first-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. Bibcode:2004EPJB...42..123B. doi:10.1140/epjb/e2004-00364-9. S2CID 14975826.

[Second-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. Bibcode:2006EPJB...49..513B. doi:10.1140/epjb/e2006-00085-1. S2CID 9862922.

[Third-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. doi:10.1061/(ASCE)WR.1943-5452.0000159.

[Fourth-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. doi:10.3141/2280-11. S2CID 110263962. Archived from the original on 2014-11-21.

[Fifth-5] Courtat, T.; Gloaguen, C.; Douady, S. (2011). "Mathematics and morphogenesis of cities: A geometrical approach". Phys. Rev. E. 83 (3): 036106. arXiv:1010.1762. Bibcode:2011PhRvE..83c6106C. doi:10.1103/PhysRevE.83.036106. PMID 21517557. S2CID 808585.

[Sixth-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. Bibcode:2013EPJB...86...74R. doi:10.1140/epjb/e2012-30235-7. S2CID 254118471.

[1]

[2]

[3]

[4]

[5]

[6]