Level structure

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

[1] 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 Li called levels, consisting of the vertices at distance i from r. Equivalently, this set may be defined by setting L0 = {r}, and then, for i > 0, defining Li to be the set of vertices that are neighbors to vertices in Li − 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 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 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.