Graph bandwidth

In graph theory, the graph bandwidth problem is to label the n vertices v_i of a graph G with distinct integers ⁠${\displaystyle f(v_{i})}$⁠ so that the quantity ${\displaystyle \max\{\,|f(v_{i})-f(v_{j})|:v_{i}v_{j}\in E\,\}}$ is minimized (E is the edge set of G).^[1] 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.^[2]

The weighted graph bandwidth problem is a generalization wherein the edges are assigned weights w_ij and the cost function to be minimized is ${\displaystyle \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 (Kaplan & Shamir 1996).