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.
Contents
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 (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:
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
Thus, for large graphs, the meshedness does not carry more information than the average degree.