---
tag: MANNXQZRG3
kind: concept
name: Graph bandwidth
aliases: [bandwidth-problem, graph-bandwidth-problem]
sources:
  - wikipedia: en:27414778@r1352725665
    locator: Graph bandwidth
    note: adopted
    mention: wikipedia://en/27414778
    sections: [Summary]
same_as:
  wikidata: Q5597073
  wikipedia: Graph bandwidth
inventory: [ETXY9TJ63M]
---

## Summary

In graph theory, the **graph bandwidth problem** may be visualized as placing the vertices of a given [[graph|00C0BR7D7H]] 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|0C4JS9RF5M]] $f(v_i)$ so that the quantity $\max\{\,| f(v_i) - f(v_j)| : v_iv_j \in E \,\}$ is minimized, where $E$ is the edge set of $G$.