topological bandwidth

tags: vertex order

equivalent to: topological bandwidth

Relations

Results

• 2013 The Power of Data Reduction: Kernels for Fundamental Graph Problems by Jansen
  • topological bandwidth – The \emph{topological bandwidth} of a graph $G$ is the minimum bandwidth over all subdivisions of $G$
• 1998 A partial $k$-arboretum of graphs with bounded treewidth by Bodlaender
  • 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$.
• 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.