bisection bandwidth

• http://parallelcomp.github.io/Lecture3.pdf
  • bisection bandwidth – (number of) links across smallest cut that divides nodes in two (nearly) equal parts
• 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
• 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.
• 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.
  • graph class grid has unbounded bisection bandwidth
  • graph class disjoint cycles has constant bisection bandwidth
  • graph class outerplanar has constant bisection bandwidth
• assumed
  • bisection bandwidth upper bounds edge connectivity by a linear function – By definition