Graph bandwidth: Difference between revisions

Revision as of 18:22, 10 December 2020

Latest revision as of 17:50, 2 July 2025

(9 intermediate revisions by 8 users not shown)

Line 1:

{{Short description|Node labeling problem in graph theory}}

In [[graph theory]], the '''graph bandwidth problem''' is to label the ''n'' vertices ''v_i'' of a graph ''G'' with distinct integers ''f''(''v_i'') so that the quantity <math>\max\{\,| f(v_i) - f(v_j)| : v_iv_j \in E \,\}</math> is minimized (''E'' is the edge set of ''G'').<ref>{{harv|Chinn|Chvátalová|Dewdney|Gibbs|1982}}</ref>

In [[graph theory]], the '''graph bandwidth problem''' is to label the ''{{mvar|n''}} [[Vertex (graph theory)|vertices]] ''{{mvar|v<{{sub>|i</sub>''}}}} of a [[Graph (discrete mathematics)|graph]] ''{{mvar|G''}} with distinct integers[[integer]]s ''{{tmath|f''(''v_i''v_i)}} so that the quantity <math>\max\{\,| f(v_i) - f(v_j)| : v_iv_j \in E \,\}</math> is minimized (''{{mvar|E''}} is the edge set of ''{{mvar|G''}}).<ref>{{harv|Chinn|Chvátalová|Dewdney|Gibbs|1982}}</ref>

The problem may be visualized as placing the vertices of a graph at distinct integer points along the ''x''-axis so that the length of the longest edge is minimized. Such placement is called '''linear graph arrangement''', '''linear graph layout''' or '''linear graph placement'''.<ref name=feige/>

The '''weighted graph bandwidth problem''' is a [[generalization]] wherein the edges are assigned [[Graph (discrete mathematics)#Weighted_graph|weights]] ''{{mvar|w<{{sub>|ij</sub>''}}}} and the [[Loss function|cost function]] to be minimized is <math>\max\{\, w_{ij} |f(v_i) - f(v_j)| : v_iv_j \in E \,\}</math>.

In terms of matrices, the (unweighted) graph bandwidth is the minimal [[bandwidth (matrix theory)|bandwidth]] of thea [[symmetric matrix]] which is thean [[adjacency matrix]] of the graph.

The bandwidth may also be defined as one less than the [[maximum clique]] size in a [[proper interval graph|proper interval]] supergraph of the given graph, chosen to minimize its clique size {{harv|Kaplan|Shamir|1996}}.

==Cyclically interval graphs==

For fixed <math>k</math> define for every <math>i</math> the set

<math>I_k(i) := [i, i+k+1)</math>. <math>G_k(n)</math> is the corresponding interval graph formed from

the intervals <math>I_k(1), I_k(2), ... I_k(n)</math>. These are '''exactly''' the proper interval

graphs of graphs having bandwidth <math>k</math>. These graphs are called

'''cyclically interval graphs''' because the intervals can be assigned to layers

<math>L_1, L_2, ... L_{k+1}</math> in cyclical order, such that the intervals of a layer don't

intersect.

Therefore, one can see the relation to the [[pathwidth]]. Pathwidth restricted graphs are minor closed but

the set of subgraphs of cyclically interval graphs are not. This follows from the fact that thrinking

degree 2 vertices may increase the bandwidth.

Alternate adding vertices on edges can decrease the bandwidth. This is known as

'''topologic bandwidth'''. Another graph measure related through the bandwidth is the

[[bisection bandwidth]].

==Bandwidth formulas for some graphs==

For several families of graphs, the bandwidth <math>\varphi(G)</math> is given by an explicit formula.

Line 67 ⟶ 88:

==See also==

*[[PathwidthCutwidth]], aand [[pathwidth]], different NP-complete optimization problemproblems involving linear layouts of graphs.

==References==

{{reflist}}

*{{Cite journal | last1 = Böttcher | first1 = J. | last2 = Pruessmann | first2 = K. P. | last3 = Taraz | first3 = A. | last4 = Würfl | first4 = A. | title = Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs | doi = 10.1016/j.ejc.2009.10.010 | journal = European Journal of Combinatorics | volume = 31 | pages = 1217–1227 | year = 2010 | issue = 5 | arxiv = 0910.3014 }}

*{{Cite journal | last1 = Chinn | first1 = P. Z. |author1-link=Phyllis Chinn| last2 = Chvátalová | first2 = J. | last3 = Dewdney | first3 = A. K. |author3-link=Alexander Dewdney| last4 = Gibbs | first4 = N. E. | title = The bandwidth problem for graphs and matrices—a survey | journal = Journal of Graph Theory | volume = 6 | pages = 223–254| year = 1982 | issue = 3 | doi = 10.1002/jgt.3190060302 }}

*{{citation

| last = Chung

Line 89 ⟶ 110:

| url = http://www.math.ucsd.edu/~fan/mypaps/fanpap/86log.PDF

}}

*{{Cite journal | last1 = Dubey | first1 = C. | last2 = Feige | first2 = U. | last3 = Unger | first3 = W. | title = Hardness results for approximating the bandwidth | journal = Journal of Computer and System Sciences | volume = 77 | pages = 62–90| year = 2010 | doi = 10.1016/j.jcss.2010.06.006 | doi-access = free }}

* {{cite book

| last = Garey

Line 112 ⟶ 133:

| arxiv = 1012.1344

}}

*{{Cite journal | last1 = Harper | first1 = L. | title = Optimal numberings and isoperimetric problems on graphs | journal = Journal of Combinatorial Theory | volume = 1 | pages = 385–393 | year = 1966 | issue = 3 | doi = 10.1016/S0021-9800(66)80059-5 | doi-access = free }}

*{{Citation

| title = Pathwidth, bandwidth, and completion problems to proper interval graphs with small cliques