Extremal and Algorithmic Results for Bipartite Graphs via Ferrers Dimension and Axis-Parallel Geometry

This thesis investigates the interplay between geometry, combinatorics, and algorithms in the study of structured graph classes arising from geometric representations. A central theme is that mild geometric restrictions often impose a strong combinatorial structure, which can be leveraged to obtain both extremal bounds and improved algorithmic guarantees for classical hard problems. The first part of the thesis studies guillotine cut separations for families of non-overlapping squares. Guillotine cuts provide a simple recursive partitioning scheme that underlies dynamic programming approaches for geometric packing and independent set problems. We prove that every instance admits a guillotine separable subset of a constant fraction of total weight, improving previous guarantees in the weighted setting and yielding a clean constant-factor approximation framework. The second part focuses on geometric bipartite graphs, where edges are defined by intersections or containments between two families of geometric objects. We establish near-tight Zarankiewicz bounds for several natural intersection bigraph classes, including graphs of low Ferrers dimension, segment--ray graphs, and grid intersection graphs. These results reveal sharp separations between low-dimensional geometric classes and demonstrate how geometric constraints fundamentally limit edge density, while avoiding bicliques. The third part addresses the Maximum Balanced Biclique problem through a bipartite analogue of perfect graph theory. We introduce the notions of cross-coloring and bi-perfectness and show that several geometric bipartite classes are almost bi-perfect, implying constant-factor approximation algorithms via semidefinite programming relaxations. Finally, we provide freeable matrix characterization of bipartite graphs of Ferrers dimension three, showing that this class is captured exactly by avoiding two finite matrix patterns. This contributes a purely combinatorial recognition framework independent of geometric representations. Overall, the thesis develops a unified perspective in which geometry induces structural sparsity and pattern restrictions, enabling new extremal results and algorithmic tools for biclique problems in bipartite intersection graphs.

Department dc:contributor.department

Tietotekniikan laitos

Grantor dc:publisher

Aalto University

Year dc:date.issued

2026

Author dc:creator

• Zarsav, Minoo

Advisors dc:contributor.advisor

• Chalermsook, Parinya, Prof., University of Sheffield, UK
• Savioja, Lauri, Prof., Aalto University, Department of Computer Science, Finland

Contributors dc:contributor

• Aalto-yliopisto
• Aalto University

Language dc:language.iso

en

Repository record dc:identifier.uri

https://aaltodoc.aalto.fi/handle/123456789/144483

OAI record oai:identifier

https://aaltodoc.aalto.fi/server/oai/request?verb=GetRecord&metadataPrefix=dim&identifier=oai%3Aaaltodoc.aalto.fi%3A123456789%2F144483