Editing Level structure

[[File:Graph level structure.svg|thumb|upright=1.3|An example for an undirected Graph with a vertex {{mvar|r}} and its corresponding level structure]]
{{hatnote|For the concept in algebraic geometry, see [[level structure (algebraic geometry)]]}}
In the [[mathematics|mathematical]] subfield of [[graph theory]] a '''level structure''' of a [[rooted graph]] is a [[Partition of a set|partition]] of the [[vertex (graph theory)|vertices]] into subsets that have the same [[distance (graph theory)|distance]] from a given root vertex.<ref name="dps">{{Cite FTP | last1 = Díaz | first1 = Josep
 | last2 = Petit | first2 = Jordi
 | last3 = Serna | first3 = Maria | author3-link = Maria Serna
 | doi = 10.1145/568522.568523
 | issue = 3
 | pages = 313–356
 | title = A survey of graph layout problems
 | url = ftp://ftp-sop.inria.fr/mascotte/personnel/Stephane.Perennes/DPS02.pdf
 | volume = 34
 | year = 2002| citeseerx = 10.1.1.12.4358
 | server = ACM Computing Surveys | s2cid = 63793863
 }}.</ref>

==Definition and construction==
Given a [[connected graph]] ''G'' = (''V'', ''E'') with ''V'' the set of  [[vertex (graph theory)|vertices]] and ''E'' the set of [[edge (graph theory)|edges]], and with a root vertex ''r'', the level structure is a partition of the vertices into subsets ''L<sub>i</sub>'' called levels, consisting of the vertices at distance ''i'' from ''r''. Equivalently, this set may be defined by setting ''L''<sub>0</sub>&nbsp;=&nbsp;{''r''}, and then, for ''i''&nbsp;>&nbsp;0, defining ''L<sub>i</sub>'' to be the set of vertices that are neighbors to vertices in ''L''<sub>''i''&nbsp;&minus;&nbsp;1</sub> but are not themselves in any earlier level.<ref name="dps"/>

The level structure of a graph can be computed by a variant of [[breadth-first search]]:<ref name="mehlhorn">{{cite book |last1=Mehlhorn |first1=Kurt |author1-link=Kurt Mehlhorn|first2=Peter |last2=Sanders|author2-link=Peter Sanders (computer scientist) |title=Algorithms and Data Structures: The Basic Toolbox |publisher=Springer |year=2008 |url=http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/GraphTraversal.pdf}}</ref>{{rp|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.<ref name="dps"/>

==Applications==
The partition of a graph into its level structure may be used as a heuristic for graph layout problems such as [[graph bandwidth]].<ref name="dps"/> The [[Cuthill–McKee algorithm]] is a refinement of this idea, based on an additional sorting step within each level.<ref>{{citation
 | last1 = Cuthill | first1 = E. | author1-link = Elizabeth Cuthill
 | last2 = McKee | first2 = J.
 | contribution = Reducing the bandwidth of sparse symmetric matrices
 | doi = 10.1145/800195.805928
 | pages = 157–172
 | publisher = ACM
 | title = Proceedings of the 1969 24th national conference (ACM '69)
 | year = 1969| s2cid = 18143635 }}.</ref>

Level structures are also used in algorithms for [[sparse matrix|sparse matrices]],<ref>{{citation
 | last = George | first = J. Alan
 | contribution = Solution of linear systems of equations: direct methods for finite element problems
 | location = Berlin
 | mr = 0440883
 | pages = 52–101. Lecture Notes in Math., Vol. 572
 | publisher = Springer
 | title = Sparse matrix techniques (Adv. Course, Technical Univ. Denmark, Copenhagen, 1976)
 | year = 1977}}.</ref> and for constructing [[planar separator theorem|separators of planar graphs]].<ref>{{citation
 | last1 = Lipton | first1 = Richard J. | author1-link = Richard J. Lipton
 | last2 = Tarjan | first2 = Robert E. | author2-link = Robert Tarjan
 | journal = SIAM Journal on Applied Mathematics
 | pages = 177–189
 | title = A separator theorem for planar graphs
 | volume = 36
 | year = 1979
 | doi = 10.1137/0136016
 | issue = 2| citeseerx = 10.1.1.214.417}}.</ref>

==References==
{{reflist}}

[[Category:Graph theory objects]]