Em teoria dos grafos, o problema da Largura de Banda de Grafos é rotular os n vértices v_i de um grafo G com inteiros distintos f(v_i), de modo que a quantidade ${\displaystyle \max\{\,|f(v_{i})-f(v_{j})|:v_{i}v_{j}\in E\,\}}$ é minimizada (E é o conjunto de arestas de G).^[1] O problema pode ser visualizado como colocar os vértices de um grafo em pontos inteiros distintos ao longo de x-eixos, de modo que o comprimento da maior banda é minimizada. Tal atribuição é chamada arranjos de grafos lineares, esboço de grafos lineares ou atribuição de grafos lineares.^[2]

O problema da Largura de Banda de Grafos com peso é a generalização em que as arestas são pesos atribuídos w_ij e a função de custo para ser minimizada é ${\displaystyle \max\{\,w_{ij}|f(v_{i})-f(v_{j})|:v_{i}v_{j}\in E\,\}}$.

Em termos de matrizes, a Largura de Banda de Grafos (sem peso) é a largura de banda da matriz simétrica que é a matriz de adjacência do grafo. A largura de banda também pode ser definida como uma menor que o tamanho do clique em um supergrafo de intervalo adequado do grafo dado, escolhido para minimizar seu tamanho de clique (Kaplan & Shamir 1996).

Para várias famílias de grafos, a largura de banda ${\displaystyle \varphi (G)}$ é dada por uma fórmula explícita.

A largura de banda de um caminho em um grafo ${\displaystyle P_{n}}$ sobre n vértices é ${\displaystyle 1}$, e para um grafo completo ${\displaystyle K_{m}}$, temos ${\displaystyle \varphi (K_{n})=n-1}$. Para o Grafo bipartido completo ${\displaystyle K_{m,n},}$

${\displaystyle \varphi (K_{m,n})=\lfloor (m-1)/2\rfloor +n}$, assumindo ${\displaystyle m\geq n\geq 1}$, a qual foi provada por Chvátal.^[3] Como um caso especial dessa fórmula, o grafo estrela ${\displaystyle S_{k}=K_{k,1}}$ em k+1 vértices tem largura de banda ${\displaystyle \varphi (S_{k})=\lfloor (k-1)/2\rfloor +1}$.

Para o grafo hipercúbico ${\displaystyle Q_{n}}$ em ${\displaystyle 2^{n}}$ vértices, a largura de banda foi determinada por Harper (1966) para ser :${\displaystyle \varphi (Q_{n})=\sum _{m=0}^{n-1}{\binom {m}{\lfloor m/2\rfloor }}.}$

Chvatálová mostrou^[4] que a largura de banda do ${\displaystyle (m\times n)}$ grafo de grade quadrada ${\displaystyle P_{m}\times P_{n}}$, isto é, o produto cartesiano de dois caminhos de grafo em ${\displaystyle m}$ e ${\displaystyle n}$ vértices, é igual à ${\displaystyle \min\{m,n\}}$.

A largura de banda de um grafo pode ser limitada em termos de vários outros parâmetros de grafos. Por exemplo, deixando χ(G) denotar o número cromático de G,

φ(G) ≥ χ(G)-1;

deixando diam(G) denotar o diâmetro de G, as desigualdades seguintes:^[5]

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

onde ${\displaystyle n}$ é o número de vértices em ${\displaystyle G}$.

Se um grafo ${\displaystyle G}$ tem largura de banda ${\displaystyle k}$, então sua largura do caminho é, no máximo, ${\displaystyle k}$ (Kaplan & Shamir 1996), e sua profundidade de árvore é, no máximo, ${\displaystyle k\log(n/k)}$ (Gruber 2012). Em contraste, como notado na seção anterior, o grafo estrela ${\displaystyle S_{k}}$, um exemplo estruturalmente muito simples de uma árvore tem largurra de banda grande, comparativamente. Observe que a largura do caminho de ${\displaystyle S_{k}}$ é 1, e sua árvore de profundidade é 2.

Algumas famílias de grafos de grau limitado tem largura de banda sublinear: Chung (1988) provado que se T é uma árvore de grau máximo no máximo ∆, então

${\displaystyle \varphi (T)\leq 5n/\log _{\Delta }n}$.

Geralmente, para grafos planares de grau máximo limitado no máximo ∆, um limite similar segue (cf. Böttcher et al. 2010):

${\displaystyle \varphi (G)\leq 20n/\log _{\Delta }n}$.

Ambas as versões com e sem peso são casos especiais do problema da atribuição quadrática do gargalo. O problema da largura de banda é NP-difícil, mesmo para alguns casos especiais.^[6] A respeito da exxistência de algoritmos de aproximação eficientes, sabe-se que a largura de banda é NP-difícil para aproximar dentro de qualquer constante, e isso vale mesmo quando os grafos de entrada são restritos para árvores cartepillar (Dubey, Feige & Unger 2010). Por outro lado, um número de casos especiais solúveis polinomialmente são conhecidos.^[2] Um algoritmo de heurística para obter esboços de grafo linear de largura de banda baixa é o algoritmo de Cuthill–McKee. Um algoritmo de multinível rápido para computação de largura de banda de grafos foi proposto em .^[7]

O interesse nesse problema vem de algumas áreas de aplicação.

Uma área é o tratamento de matriz esparsa/matriz de banda, e algoritmos gerais dessa área, tal como o algoritmo de Cuthill–McKee, pode ser aplicado para encontrar soluções aproximadas para o problema da largura de banda de grafo.

Outro domínio de aplicação é em automação de design eletrônico. Na metodologia do design de célula padrão, tipicamente células padrão têm a mesma altura, e sua atribuição é organizada em um número de linhas. Nesse contexto(modelos do problema de largura de banda de grafo), o problema da atribuição de um conjuntp de células padrão em uma única linha com o objetivo de minimizar o delay de propagação máximo (o qual é assumido ser proporcional ao comprimento do arame).

• Largura do caminho, um problema de otimização NP-completo diferente envolvendo esboços lineares de grafos.

• Böttcher, Julia; Klaas P. (1 de julho de 2010). «Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs». European Journal of Combinatorics. 31 (5): 1217-1227. doi:10.1016/j.ejc.2009.10.010  A referência emprega parâmetros obsoletos |coautores= (ajuda)
• Chinn, P. Z.; J. (1 de setembro de 1982). «The bandwidth problem for graphs and matrices—a survey». Journal of Graph Theory (em inglês). 6 (3): 223-254. ISSN 1097-0118. doi:10.1002/jgt.3190060302  A referência emprega parâmetros obsoletos |coautores= (ajuda)
• Chung, Fan R. K. (1988), «Labelings of Graphs», in: Beineke, Lowell W., Selected Topics in Graph Theory (PDF), ISBN 978-0-12-086203-0, Academic Press, pp. 151–168  Faltam os |sobrenomes1= em Editors list (ajuda)
• Dubey, Chandan; Uriel (1 de janeiro de 2011). «Hardness results for approximating the bandwidth». Journal of Computer and System Sciences. 77 (1): 62-90. doi:10.1016/j.jcss.2010.06.006  A referência emprega parâmetros obsoletos |coautores= (ajuda)
• Garey, M.R.; Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. ISBN 0-7167-1045-5 
• Gruber, Hermann (2012), «On Balanced Separators, Treewidth, and Cycle Rank», Journal of Combinatorics, 3 (4): 669–682, doi:10.4310/joc.2012.v3.n4.a5 
• Harper, L.H. «Optimal numberings and isoperimetric problems on graphs». Journal of Combinatorial Theory. 1 (3): 385-393. doi:10.1016/s0021-9800(66)80059-5 
• Kaplan, Haim; Shamir, Ron (1996), «Pathwidth, bandwidth, and completion problems to proper interval graphs with small cliques», SIAM Journal on Computing, 25: 540–561, doi:10.1137/s0097539793258143 

• Minimum bandwidth problem, em: Pierluigi Crescenzi and Viggo Kann (eds.), A compendium of NP optimization problems. Acessado em Maio 26, 2010.