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.

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. 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
and that if there are m edges then the number of bounded faces is m − n + 1.
Therefore, a normalized meshedness coefficient can be defined as the ratio of these two numbers:
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. It has also been used to characterize the network structure of streets in urban areas.

Limitations

Using the definition of the average degree, one can see that in the limit of large graphs (number of edges the meshedness tends to
Thus, for large graphs, the meshedness does not carry more information than the average degree.