Level structure
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.[1]
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.0 1.1 1.2 1.3 Díaz, Josep; Petit, Jordi (2002), "A survey of graph layout problems", ACM Computing Surveys 34 (3): 313–356, doi:10.1145/568522.568523, ftp://ftp-sop.inria.fr/mascotte/personnel/Stephane.Perennes/DPS02.pdf.
- ↑ Mehlhorn, Kurt; Sanders, Peter (2008). Algorithms and Data Structures: The Basic Toolbox. Springer. http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/GraphTraversal.pdf.
- ↑ "Reducing the bandwidth of sparse symmetric matrices", Proceedings of the 1969 24th national conference (ACM '69), ACM, 1969, pp. 157–172, doi:10.1145/800195.805928.
- ↑ 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.
- ↑ "A separator theorem for planar graphs", SIAM Journal on Applied Mathematics 36 (2): 177–189, 1979, doi:10.1137/0136016.
 |  |
