Restricted cuts for bisections in solid grids: A proof via polygons

Abstract

The graph bisection problem asks to partition the n vertices of a graph into two sets of equal size so that the number of edges across the cut is minimum. We study nite, connected subgraphs of the innite twodimensional grid that do not have holes. Since bisection is an intricate problem, our interest is in the tradeo between runtime and solution quality that we get by limiting ourselves to a special type of cut, namely cuts with at most one bend each (corner cuts). We prove that optimum corner cuts get us arbitrarily close to equal sized parts, and that this limitation makes us lose only a constant factor in the quality of the solution. We obtain our result by a thorough study of cuts in polygons and the eect of limiting these to corner cuts.