level structure

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 L_i called levels, consisting of the vertices at distance i from r. Equivalently, this set may be defined by setting L₀ = {r}, and then, for i > 0, defining L_i to be the set of vertices that are neighbors to vertices in L_i − 1 but are not themselves in any earlier level.

The level structure of a graph can be computed by a variant of breadth-first search:{{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}}{{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'

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.

The partition of a graph into its level structure may be used as a heuristic for graph layout problems such as graph bandwidth. The Cuthill–McKee algorithm is a refinement of this idea, based on an additional sorting step within each level.{{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 }}.

Level structures are also used in algorithms for sparse matrices,{{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}}. and for constructing separators of planar graphs.{{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}}.

{{reflist}}

Category:Graph theory objects