Level structure

<h2 id="definition-and-construction">Definition and construction</h2>
Given a <a href="/facts/Connected_graph/FSNjsYhz">connected graph</a> G = (V, E) with V the set of <a href="/facts/Vertex_(graph_theory)/WhlWmL3o">vertices</a> and E the set of <a href="/facts/Edge_(graph_theory)/W0MqKkyE">edges</a>, 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.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a>
The level structure of a graph can be computed by a variant of <a href="/facts/Breadth-first_search/2kulDXCx">breadth-first search</a>:<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>: 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'

<h2 id="properties">Properties</h2>
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.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>

<h2 id="applications">Applications</h2>
The partition of a graph into its level structure may be used as a heuristic for graph layout problems such as <a href="/facts/Graph_bandwidth/ugGo2j8l">graph bandwidth</a>.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> The <a href="/facts/Cuthill%E2%80%93McKee_algorithm/ab5ekCXk">Cuthill–McKee algorithm</a> is a refinement of this idea, based on an additional sorting step within each level.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>
Level structures are also used in algorithms for <a href="/facts/Sparse_matrix/FFtN0XjR">sparse matrices</a>,<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a> and for constructing <a href="/facts/Planar_separator_theorem/IfwGC9y3">separators of planar graphs</a>.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a>

<h2 id="references">References</h2>

<ol>
<li id="fn: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. <a href="/wiki/Maria_Serna" target="_blank">/wiki/Maria_Serna</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">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. <a href="/wiki/Maria_Serna" target="_blank">/wiki/Maria_Serna</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Mehlhorn, Kurt; Sanders, Peter (2008). Algorithms and Data Structures: The Basic Toolbox (PDF). Springer. <a href="/wiki/Kurt_Mehlhorn" target="_blank">/wiki/Kurt_Mehlhorn</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">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. <a href="/wiki/Maria_Serna" target="_blank">/wiki/Maria_Serna</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">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. <a href="/wiki/Maria_Serna" target="_blank">/wiki/Maria_Serna</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">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. <a href="/wiki/Elizabeth_Cuthill" target="_blank">/wiki/Elizabeth_Cuthill</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">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. <a href="/wiki/MR_(identifier)" target="_blank">/wiki/MR_(identifier)</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">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. <a href="/wiki/Richard_J._Lipton" target="_blank">/wiki/Richard_J._Lipton</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
</ol>

Level structure open-in-new

Level structure