Level structure

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₀ = {r}, 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.[1]

The level structure of a graph can be computed by a variant of breadth-first search:[2]^: 176

algorithm level-BFS(G, r):
    Q ← {r}
    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'

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.[1]

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

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