Reference articles on history, science, culture and more
Surprise meSurprise meSubscribe
Encyclopedia

Graph bandwidth

Node labeling problem in graph theory

Wikipedia contributorsAdapted for Fathomly · View authors
3 min read
Source updated May 5, 2026

In graph theory, the graph bandwidth problem may be visualized as placing the vertices of a given graph at distinct integer positions along the number line so that the length of the longest edge is minimized. Such placement is called linear graph arrangement, linear graph layout or linear graph placement. It may be formalized as labeling the n vertices v_{i} of a graph G with distinct integers f(v_{i}) so that the quantity \max\{\,|f(v_{i})-f(v_{j})|:v_{i}v_{j}\in E\,\} is minimized, where E is the edge set of G.

The weighted graph bandwidth problem is a generalization wherein the edges are assigned weights w_{ij} and the cost function to be minimized is the product of weight with length, \max\{\,w_{ij}|f(v_{i})-f(v_{j})|:v_{i}v_{j}\in E\,\}.

In terms of matrices, the (unweighted) graph bandwidth is the minimal bandwidth of a symmetric matrix which is an adjacency matrix of the graph. The bandwidth may also be defined as one less than the maximum clique size in a proper interval supergraph of the given graph, chosen to minimize its clique size.

01Bandwidth formulas for some graphs

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

The bandwidth of a path graph P_{n} on n vertices is 1, and the bandwidth of a complete graph K_{m} is \varphi (K_{n})=n-1. For the complete bipartite graph K_{m,n}, \varphi (K_{m,n})=\lfloor (m-1)/2\rfloor +n, assuming m\geq n\geq 1. As a special case of this formula, the star graph S_{k}=K_{k,1} on k+1 vertices has bandwidth \varphi (S_{k})=\lfloor (k-1)/2\rfloor +1.

For the hypercube graph Q_{n} on 2^{n} vertices the bandwidth is \varphi (Q_{n})=\sum _{m=0}^{n-1}{\binom {m}{\lfloor m/2\rfloor }}.

The bandwidth of the m\times n square grid graph P_{m}\times P_{n}, that is, the Cartesian product of two path graphs on m and n vertices, is equal to \min\{m,n\}.

02Bounds

The bandwidth of a graph can be bounded in terms of various other graph parameters. For instance, letting χ(G) denote the chromatic number of G,

\varphi (G)\geq \chi (G)-1;

letting diam(G) denote the diameter of G, the following inequalities hold:

\lceil (n-1)/\operatorname {diam} (G)\rceil \leq \varphi (G)\leq n-\operatorname {diam} (G),

where n is the number of vertices in G.

If a graph G has bandwidth k, then its pathwidth is at most k, and its tree-depth is at most k log(n/k). In contrast, as noted in the previous section, the star graph Sk, a structurally very simple example of a tree, has comparatively large bandwidth. Observe that the pathwidth of Sk is 1, and its tree-depth is 2.

Some graph families of bounded degree have sublinear bandwidth: if T is a tree of maximum degree at most ∆, then

\varphi (T)\leq {\frac {5n}{\log _{\Delta }n}}.

More generally, for planar graphs of bounded maximum degree at most ∆, a similar bound holds:

\varphi (G)\leq {\frac {20n}{\log _{\Delta }n}}.

03Computing the bandwidth

Both the unweighted and weighted versions are special cases of the quadratic bottleneck assignment problem. The bandwidth problem is NP-hard, even for some special cases. Regarding the existence of efficient approximation algorithms, it is known that the bandwidth is NP-hard to approximate within any constant, and this even holds when the input graphs are restricted to caterpillar trees with maximum hair length 2. For arbitrary graphs with n vertices, the best approximation ratio known is O(\log ^{3}n{\sqrt {\log \log n}}), using semidefinite programming. For the case of dense graphs, a 3-approximation algorithm is known. On the other hand, a number of polynomially-solvable special cases are known. A heuristic algorithm for obtaining linear graph layouts of low bandwidth is the Cuthill-McKee algorithm. Fast multilevel algorithm for graph bandwidth computation was proposed in.

04Applications

The interest in this problem comes from some application areas.

One area is sparse matrix/band matrix handling, and general algorithms from this area, such as Cuthill-McKee algorithm, may be applied to find approximate solutions for the graph bandwidth problem.

Another application domain is in electronic design automation. In standard cell design methodology, typically standard cells have the same height, and their placement is arranged in a number of rows. In this context, graph bandwidth problem models the problem of placement of a set of standard cells in a single row with the goal of minimizing the maximal propagation delay (which is assumed to be proportional to wire length).

Watch videos about Graph bandwidthExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Graph bandwidth”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.

Continue exploring

Related topics

Cutwidth

In graph theory, the cutwidth of an undirected graph is the smallest integer k {\displaystyle k} with the following property: there is an ordering of the vertices of the graph, such that every cut obtained by partitioning the vertices into earlier and later subsets of the ordering is crossed by at most k {\displaystyle k} edges. That is, if the vertices are numbered v 1 , v 2 , … v n {\displaystyle v_{1},v_{2},\dots v_{n}} , then for every ℓ = 1 , 2 , … n − 1 {\displaystyle \ell =1,2,\dots n-1} , the number of edges v i v j {\displaystyle v_{i}v_{j}} with i ≤ ℓ {\displaystyle i\leq \ell } and j > ℓ {\displaystyle j>\ell } is at most k {\displaystyle k} .

Pathwidth

In graph theory, a path decomposition of a graph G is, informally, a representation of G as a "thickened" path graph, and the pathwidth of G is a number that measures how much the path was thickened to form G. More formally, a path-decomposition is a sequence of subsets of vertices of G such that the endpoints of each edge appear in one of the subsets and such that each vertex appears in a contiguous subsequence of the subsets, and the pathwidth is one less than the size of the largest set in such a decomposition. Pathwidth is also known as interval thickness, vertex separation number, or node searching number.