topological bandwidth

• 2013 Jansen2013
  • topological bandwidth – The \emph{topological bandwidth} of a graph $G$ is the minimum bandwidth over all subdivisions of $G$
• 1998 Bodlaender1998
  • page 22 : topological bandwidth – The \emph{topological bandwidth} of a graph $G$ is the minimum bandwidth over all graphs $G’$ which are obtained by addition of an arbitrary number of vertices along edges of $G$.
  • page 23 : topological bandwidth $k$ upper bounds pathwidth by $\mathcal O(k)$ – Theorem 45. For every graph $G$, the pathwidth of $G$ is at most the topological band-width of $G$.
• unknown
  • topological bandwidth $k$ upper bounds bisection bandwidth by $\mathcal O(k)$ – Order vertices by their bandwidth integer. We split the graph in the middle of this ordering. There are at most roughly $k^2/2$ edges over this split.
  • bandwidth $k$ upper bounds topological bandwidth by $\mathcal O(k)$ – By definition