Level structure

In the mathematical subfield of graph theory a level structure of an undirected graph is a partition of the vertices into subsets that have the same distance from a given root vertex..

Definition and construction

Given a connected graph ''G'' = (''V'', ''E'') with ''V'' the set of vertices and ''E'' the set of edges, and with a root vertex ''r'', the level structure is a partition of the vertices into subsets ''L_i'' called levels, consisting of the vertices at distance ''i'' from ''r''. Equivalently, this set may be defined by setting ''L''₀ = , and then, for ''i'' > 0, defining ''L_i'' to be the set of vertices that are neighbors to vertices in ''L''_{''i'' − 1} but are not themselves in any earlier level.

The level structure of a graph can be computed by a variant of breadth-first search:

algorithm level-BFS(G, r):
Q ←
for ℓ from 0 to ∞:
process(Q, ℓ) ''// the set Q holds all vertices at level ℓ''
mark all vertices in Q as discovered
Q' ←
for u in Q:
for each edge (u, v):
if v is not yet marked:
add v to Q'
if Q' is empty:
return
Q ← Q'

Properties

In a level structure, each edge of ''G'' either has both of its endpoints within the same level, or its two endpoints are in consecutive levels.

Applications

The partition of a graph into its level structure may be used as a heuristic for graph layout problems such as graph bandwidth. The Cuthill–McKee algorithm is a refinement of this idea, based on an additional sorting step within each level.

Level structures are also used in algorithms for sparse matrices, and for constructing separators of planar graphs..

References

{{reflist

Graph theory objects