Level structure

Last updated
An example for an undirected Graph with a vertex r and its corresponding level structure Graph level structure.svg
An example for an undirected Graph with a vertex r and its corresponding 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]

Contents

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. [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'

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

Applications

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]

References

  1. 1 2 3 4 Díaz, Josep; Petit, Jordi; Serna, Maria (2002). "A survey of graph layout problems" (PDF). ACM Computing Surveys (FTP). pp. 313–356. CiteSeerX   10.1.1.12.4358 . doi:10.1145/568522.568523. S2CID   63793863.(To view documents see Help:FTP).
  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 .
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.