In
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, the meshedness coefficient is a
graph invariant
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
* Graph (topology), a topological space resembling a graph in the sense of discr ...
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
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are u ...
to 1 for
maximal planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cros ...
s.
[
]
[
]
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
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are u ...
, planar graphs with no cycle.
The other extreme is represented by
maximal planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cros ...
s, 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 2''n'' − 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
In graph theory, a branch of mathematics, the circuit rank, cyclomatic number, cycle rank, or nullity of an undirected graph is the minimum number of edges that must be removed from the graph to break all its cycles, making it into a tree or fo ...
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
The algebraic connectivity (also known as Fiedler value or Fiedler eigenvalue after Miroslav Fiedler) of a graph ''G'' is the second-smallest eigenvalue (counting multiple eigenvalues separately) of the Laplacian matrix of ''G''. This eigenvalue i ...
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.
References
{{reflist
Graph invariants
Planar graphs