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 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. The level structure of a graph can be computed by a variant of breadth-first search: 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' 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 Graph theory objects