The focus of this research is the study of constrained cuts in graphs, with special emphasis on the characterization of edge-isoperimetric structures in subclasses such as multidimensional arrays and tori, and the related computational complexity of constrained edge-boundary calculations in planar graphs. Classically, isoperimetric inequalities provide estimates about how large a quantity such as the volume of a body can be, given only its surface area. The discrete analogue of this notion applied to graphs measures types of connectivity of the graph and has many important applications in algorithm design. Despite the extensive literature on this subject, algorithmic complexity of fundamental questions such as planar graph partitioning and the problem of the identification of edge-isoperimetric sets in highly structured product graphs are not completely understood. The main problems investigated in this project include: (1) study of the exact computational complexity of various graph partitioning problems in planar graphs, (2) study of invariants such as the edge-isoperimetric number for general classes of high dimensional arrays and tori. Preliminary results have been on special types of multidimensional arrays, and made use of compression, layout techniques, and graph embedding. In addition to being of theoretical interest, a deeper understanding of these issues may result in improved algorithms for routing, scheduling, VLSI layout, and other applications.
