topological bandwidth

• 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 upper bounds pathwidth by a linear function – Theorem 45. For every graph $G$, the pathwidth of $G$ is at most the topological band-width of $G$.
• Jansen2013
  • topological bandwidth – The \emph{topological bandwidth} of a graph $G$ is the minimum bandwidth over all subdivisions of $G$
• assumed
  • bandwidth upper bounds topological bandwidth by a linear function – By definition
• unknown source
  • topological bandwidth upper bounds bisection bandwidth by a linear function – 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.