bisection bandwidth

• 2022/09 Tran2022
  • page 34 : bounded c-closure does not imply bounded bisection bandwidth – Proposition 5.5. $c$-Closure is incomparable to Bisection Width.
  • page 34 : bounded bisection bandwidth does not imply bounded c-closure – Proposition 5.5. $c$-Closure is incomparable to Bisection Width.
  • page 40 : bounded twin-width does not imply bounded bisection bandwidth – Observation 6.9. Twin-width is incomparable to Bisection Width.
  • page 40 : bounded bisection bandwidth does not imply bounded twin-width – Observation 6.9. Twin-width is incomparable to Bisection Width.
• https://en.wikipedia.org/wiki/Bisection_bandwidth
  • bisection bandwidth – … bisected into two equal-sized partitions, the bisection bandwidth of a network topology is the bandwidth available between the two partitions.
• http://parallelcomp.github.io/Lecture3.pdf
  • bisection bandwidth – (number of) links across smallest cut that divides nodes in two (nearly) equal parts
• 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.
  • bisection bandwidth $k$ upper bounds edge connectivity by $\mathcal O(k)$ – By definition
  • graph class grid has unbounded bisection bandwidth
  • disjoint cycles upper bounds bisection bandwidth by a constant
  • outerplanar upper bounds bisection bandwidth by a constant
• SchroderThesis
  • page 24 : bounded vertex cover does not imply bounded bisection bandwidth – Proposition 3.20
  • page 28 : bounded maximum degree does not imply bounded bisection bandwidth – Proposition 3.26
  • page 28 : bounded distance to bipartite does not imply bounded bisection bandwidth – Proposition 3.26
  • page 30 : bounded bisection bandwidth does not imply bounded domatic number – Proposition 3.28
  • page 30 : bounded feedback edge set does not imply bounded bisection bandwidth – Proposition 3.29
  • page 33 : bounded bisection bandwidth does not imply bounded chordality – Proposition 3.31
  • page 33 : bounded bisection bandwidth does not imply bounded clique-width – Proposition 3.32
  • page 33 : bounded bisection bandwidth does not imply bounded maximum clique – Proposition 3.33