97-53: Rectangle Breaking in Grids

DIMACS TR: 97-53

Rectangle Breaking in Grids

Authors: Paul A. Dreyer, Jr. and Therese C. Biedl

ABSTRACT
Given an $n \times n$ square grid, there are the outlines of $n^2$ $1 \times 1$ squares, $(n-1)^2$ $2 \times 2$ squares, and so on. What is the minimum number of edges that can be removed from the grid such that there is no complete outline of a square remaining? Using techniques from tiling problems and other graph theoretic methods, we solve the problem for all $n$ and prove similar results for rectangular grids for which the side lengths differ by no more than six. We also introduce another version of the problem where we ask for the minimum number of edges to ``break'' all of the rectangles in a grid.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-53.ps.gz

DIMACS Home Page