Ph.D Thesis | |

Ph.D Student | Ackerman Eyal |
---|---|

Subject | Counting Problems for Geometric Structures: Rectangulations, Floorplans, and Quasi-Planar Graphs |

Department | Department 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*(18* ^{n}*/

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.