Misplaced Pages

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.

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₀ = {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.

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

1. ^ Díaz, Josep; Petit, Jordi; Serna, Maria (2002), "A survey of graph layout problems" (PDF), ACM Computing Surveys, 34 (3): 313–356, CiteSeerX 10.1.1.12.4358, doi:10.1145/568522.568523, S2CID 63793863.
2. Mehlhorn, Kurt; Sanders, Peter (2008). Algorithms and Data Structures: The Basic Toolbox (PDF). Springer.
3. Cuthill, E.; McKee, J. (1969), "Reducing the bandwidth of sparse symmetric matrices", Proceedings of the 1969 24th national conference (ACM '69), ACM, pp. 157–172, doi:10.1145/800195.805928, S2CID 18143635.
4. George, J. Alan (1977), "Solution of linear systems of equations: direct methods for finite element problems", Sparse matrix techniques (Adv. Course, Technical Univ. Denmark, Copenhagen, 1976), Berlin: Springer, pp. 52–101. Lecture Notes in Math., Vol. 572, MR 0440883.
5. Lipton, Richard J.; Tarjan, Robert E. (1979), "A separator theorem for planar graphs", SIAM Journal on Applied Mathematics, 36 (2): 177–189, CiteSeerX 10.1.1.214.417, doi:10.1137/0136016.

• Graph theory objects