El problema de ancho de banda en grafos, donde se busca una etiquetación de los vértices del grafo que dé la mínima diferencia entre las etiquetas sobre todas las aristas, es un problema clásico NP-duro que ha atraído mucha atención en las últimas décadas. En este artículo, nos enfocamos en el llamado (EPA) introducido por Blum et al. en 2000, que en su mayor parte debe resolver una relajación de programación semidefinida con un número exponencial de restricciones lineales. Presentamos varias propiedades teóricas de este problema especial de programación semidefinida (SDP) y un algoritmo tipo plano de corte para resolverlo, que funciona de manera muy eficiente en combinación con métodos de puntos interiores o con el método de paquetes. Resultados numéricos extensos demuestran que este algoritmo, que hasta ahora solo ha sido estudiado teóricamente, en la práctica proporciona una muy buena etiquetación para grafos con .