Ph.D Thesis

Ph.D StudentAckerman Eyal
SubjectCounting Problems for Geometric Structures: Rectangulations,
Floorplans, and Quasi-Planar Graphs
DepartmentDepartment of Computer Science
Supervisors PROF. Gill Barequet
PROF. Ron Pinter


The work presented in this thesis lies within the field of Combinatorial Geometry. This field, roughly speaking, deals with questions of enumeration, existence, and properties of discrete geometric structures involving geometric objects such as points, lines, polygons, etc. Given a well-defined set of combinatorial structures, a natural question to ask, is: "how large is this set?" We first study this problem for rectangulations of a set of points in the plane. Given a set P of n points within a rectangle R in the plane, a rectangulation of P is a subdivision of R into smaller rectangles by axis-parallel segments such that every point is on a different segment. We show that when the relative order of the points forms a separable permutation, the number of rectangulations is exactly the number of Baxter permutations on n+1 elements. We also show that regardless of the order of the points, the number of guillotine rectangulations is always the n'th Schröder number, and the total number of rectangulations is O(18n/n4).

Related combinatorial structures we have investigated are floorplans - rectangular partitions with no point constraints. A floorplan represents the relative location of modules on an integrated circuit. It is known that the number of floorplans equals the number of Baxter permutations. We present a simple and efficient bijection between Baxter permutations and floorplans, which also suggests an enumeration of floorplans according to various structural parameters.

We also consider a generalization of floorplans to three and higher dimensions. The special case of guillotine partitions is analyzed, and we present both an exact summation formula for their number, as well as an analysis of its asymptotic behavior. Such partitions play an important role in many research areas and application domains, e.g., computational geometry, computer graphics, and solid modeling, to mention just a few.

Finally, we study the following problem in extremal combinatorial geometry. A topological graph is called k-quasi-planar if it does not contain k pairwise-crossing edges.  It is conjectured that for every fixed k, the maximum number of edges in a
k-quasi-planar graph on n vertices is O(n). We provide, for the first time, an affirmative answer for the case k=4. We also give the simplest proof and the best upper bound known for the maximum number of edges in 3-quasi-planar graphs on n vertices. Moreover, we show a tight upper bound for 3-quasi-planar graphs in which every pair of edges meet at most once.