A "rectangular layout" L is a partition of a rectangle into a set of disjoint smaller rectangles by vertical and horizontal line segments. L is said to "represent a graph G" if the smaller rectangles correspond to the vertices of G one-to-one, and two vertices are adjacent in G if and only if their corresponding rectangles share a common boundary in L. An "area assignment function" of L is a specification of the area of each rectangle in L. L is called a "rectangular cartogram" if the areas of the rectangles in L equal to their specified areas. L is called "area-universal" if it can realize any area-assignment function.
Rectangular layouts have applications in VLSI, architectural design, computational geometry, geographic information system, and other practical fields. Extensive research works have been done in this area. But many interesting problems remain open. The PI will study several open algorithmic problems related to these structures: (1) How to decide if a given graph G has an area-universal layout? (2) Given an area-universal layout L and an area-assignment function a, how to compute the coordinates of the cartogram for a by using a combinatorial algorithm? (3) Not all plane graphs have rectangular layouts. If G does not have one, how to find a representation of G by using recti-linear polygons of more complex shapes? (4) Another useful subclass of rectangular layouts are "slicing floorplans". Many optimization problems are NP-complete for general floorplans, but polynomial time solvable for slicing floorplans. How to decide if a given graph G has slicing floorplans or not?
The PI aims to develop efficient algorithms for solving these problems. This research will make both theoretical and practical contributions. On the practical side, many problems discussed above are motivated by real-world applications. On the theoretical side, the algorithmic tools developed in this project include several important graph-theoretic constructions, and are related to some open questions in graph theory and combinatorics. While the four problems outlined above are interesting and important, they are by no means the only problems in this field. The techniques developed in this research are likely useful in solving related problems. Two graduate students will work on this project under PI's supervision. The topics covered in this research will be taught in an advanced algorithm course.
