An \(O(n^4)\) Time Algorithm to Compute the Bisection Width of Solid Grid Graphs
The bisection problem asks for a partition of the \(n\) vertices of a graph into two sets of size at most\(\lceil n/2\rceil \), so that the number of edges connecting the sets is minimised. A grid graph is a finite connected subgraph of the infinite two-dimensional grid. It is called solid if it has no holes. Papadimitriou and Sideri (Theory Comput Syst 29:97110, 1996) gave an \(O(n^5)\) time algorithm to solve the bisection problem on solid grid graphs. We propose a novel approach that exploits structural properties of optimal cuts within a dynamic program. We show that our new technique leads to an \(O(n^4)\) time algorithm.
bisection solid grid graphs planar graphs