imported>Old Man Consequences: stub sort

2025-11-11T15:52:07Z

stub sort

← Previous revision		Revision as of 15:52, 11 November 2025
Line 1:		Line 1:
			{{Short description\|Object in graph theory}}
	[[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]]		[[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)]]}}		{{hatnote\|For the concept in algebraic geometry, see [[level structure (algebraic geometry)]]}}
Line 70:		Line 71:

	[[Category:Graph theory objects]]		[[Category:Graph theory objects]]

			{{graph-stub}}

imported>GreenC bot: Move 1 url. Wayback Medic 2.5 per WP:URLREQ#citeftp

2025-05-27T11:10:26Z

Move 1 url. Wayback Medic 2.5 per WP:URLREQ#citeftp

New page

[[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 ''Li'' called levels, consisting of the vertices at distance ''i'' from ''r''. Equivalently, this set may be defined by setting ''L''0 = {''r''}, and then, for ''i'' > 0, defining ''Li'' to be the set of vertices that are neighbors to vertices in ''L''''i'' − 1 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]]

Level structure - Revision history

imported>Old Man Consequences: stub sort

imported>GreenC bot: Move 1 url. Wayback Medic 2.5 per WP:URLREQ#citeftp