{"id":{"repo_id":"aalto","oai_identifier":"oai:aaltodoc.aalto.fi:123456789/144483"},"canonical_url":"https://search.dev.ndltd.org/etd/aalto/oai:aaltodoc.aalto.fi:123456789/144483","repository":{"repo_id":"aalto","name":"Aalto University","base_url":"https://aaltodoc.aalto.fi/server/oai/request"},"display":{"title":"Extremal and Algorithmic Results for Bipartite Graphs via Ferrers Dimension and Axis-Parallel Geometry","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Zarsav, Minoo"],"institution":"Aalto University","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Tietotekniikan laitos","school":null,"contributors":["Aalto-yliopisto","Aalto University"],"advisors":["Chalermsook, Parinya, Prof., University of Sheffield, UK","Savioja, Lauri, Prof., Aalto University, Department of Computer Science, Finland"],"committee_chairs":[],"committee_members":[],"year":2026,"date_issued":"2026","date_published":"2026","updated_at":"2026-08-21T22:21:56Z","subjects":[],"languages":["en"],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://aaltodoc.aalto.fi/handle/123456789/144483","outbound_label":"Repository record","outbound_source":"dc:identifier.uri"},"source_record":{"url":"https://aaltodoc.aalto.fi/server/oai/request?verb=GetRecord&metadataPrefix=dim&identifier=oai%3Aaaltodoc.aalto.fi%3A123456789%2F144483","prefix":"dim"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Aalto-yliopisto","Aalto University"]},{"key":"dc:contributor.advisor","label":"Advisor","values":["Chalermsook, Parinya, Prof., University of Sheffield, UK"]},{"key":"dc:contributor.department","label":"Department","values":["Tietotekniikan laitos","Department of Computer Science"]},{"key":"dc:contributor.supervisor","label":"Supervisor","values":["Savioja, Lauri, Prof., Aalto University, Department of Computer Science, Finland"]},{"key":"dc:creator","label":"Author","values":["Zarsav, Minoo"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2026-05-19T09:01:13Z"]},{"key":"dc:date.issued","label":"Date","values":["2026"]},{"key":"dc:publisher","label":"Institution","values":["Aalto University","Aalto-yliopisto"]},{"key":"dc:type","label":"Dc Type","values":["G5 Artikkeliväitöskirja"]},{"key":"dc:type.dcmitype","label":"Dc Type Dcmitype","values":["text"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://aaltodoc.aalto.fi/handle/123456789/144483"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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.","Tässä väitöskirjassa tutkitaan geometrian, kombinatoriikan ja algoritmien vuorovaikutusta rakenteellisissa graafiluokissa, jotka syntyvät geometrisista esityksistä. Keskeinen havainto on, että lievät geometriset rajoitteet pakottavat usein vahvan kombinatorisen rakenteen, jota voidaan hyödyntää sekä ekstremaalisissa rajoissa että paremmissa algoritmisissa takuissa klassisille vaikeille ongelmille. Väitöskirjan ensimmäinen osa käsittelee guillotine-leikkauserotteluja ei-päällekkäisten neliöiden perheille. Guillotine-leikkaukset tarjoavat yksinkertaisen rekursiivisen ositusmenetelmän, joka muodostaa dynaamiseen ohjelmointiin perustuvien lähestymistapojen perustan geometrisessa pakkauksessa ja riippumattoman joukon ongelmissa. Osoitamme, että jokainen instanssi sisältää guillotine-eroteltavan osajoukon, joka säilyttää vakio-osuuden kokonaispainosta. Tämä parantaa aiempia tuloksia painotetussa tapauksessa ja tuottaa selkeän vakio-kertoimisen approksimaatiokehyksen. Toinen osa keskittyy geometrisiin kaksiosaisiin graafeihin, joissa särmät määrittyvät kahden geometrisen objektiperheen välisten leikkausten tai sisältymisten perusteella. Johdamme lähes tiukat Zarankiewicz-rajat useille luonnollisille leikkausbigraafiluokille, mukaan lukien matalan Ferrers-dimension graafit, segmentti--säde-graafit sekä ruudukon leikkausgraafit. Tulokset paljastavat selkeitä eroja mataladimensionaalisten geometrialuokkien välillä ja osoittavat, kuinka geometriset rajoitteet perustavanlaatuisesti rajoittavat särmätiheyttä samalla kun suuret biklikit vältetään. Kolmas osa tarkastelee maksimaalisen tasapainoisen biklikin ongelmaa kaksiosaisena analogiana täydellisten graafien teorialle. Esittelemme käsitteet ristiväritys ja bi-perfektiys sekä osoitamme, että useat geometriset kaksiosaiset luokat ovat lähes bi-perfektejä. Tämä johtaa vakio-kertoimisiin approksimaatioalgoritmeihin semidefiniittisten ohjelmointirelaksaatioiden avulla. Lopuksi annamme ns. freeable-matriisikarakterisaation kaksiosaisille graafeille, joiden Ferrers-dimensio on kolme. Osoitamme, että tämä luokka voidaan kuvata täsmällisesti kahden äärellisen matriisikuviokiellon avulla. Tämä tuottaa puhtaasti kombinatorisen tunnistuskehyksen, joka ei riipu geometrisista esityksistä. Yhteenvetona väitöskirja kehittää yhtenäisen näkökulman, jossa geometria tuottaa rakenteellista harvuutta ja kuviorajoitteita, mahdollistaen uusia ekstremaalisia tuloksia sekä algoritmisia työkaluja biklikkiongelmiin kaksiosaisissa leikkausgraafeissa."]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Extremal and Algorithmic Results for Bipartite Graphs via Ferrers Dimension and Axis-Parallel Geometry","Ekstremaalisia ja algoritmisia tuloksia bipartite-graafeista Ferrers-dimension ja axis-parallel -geometrian kautta"]}]}],"canonical_facts":{"dc:contributor":["Aalto-yliopisto","Aalto University"],"dc:contributor.advisor":["Chalermsook, Parinya, Prof., University of Sheffield, UK"],"dc:contributor.department":["Tietotekniikan laitos","Department of Computer Science"],"dc:contributor.supervisor":["Savioja, Lauri, Prof., Aalto University, Department of Computer Science, Finland"],"dc:creator":["Zarsav, Minoo"],"dc:date.accessioned":["2026-05-19T09:01:13Z"],"dc:date.issued":["2026"],"dc:description.abstract":["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.","Tässä väitöskirjassa tutkitaan geometrian, kombinatoriikan ja algoritmien vuorovaikutusta rakenteellisissa graafiluokissa, jotka syntyvät geometrisista esityksistä. Keskeinen havainto on, että lievät geometriset rajoitteet pakottavat usein vahvan kombinatorisen rakenteen, jota voidaan hyödyntää sekä ekstremaalisissa rajoissa että paremmissa algoritmisissa takuissa klassisille vaikeille ongelmille. Väitöskirjan ensimmäinen osa käsittelee guillotine-leikkauserotteluja ei-päällekkäisten neliöiden perheille. Guillotine-leikkaukset tarjoavat yksinkertaisen rekursiivisen ositusmenetelmän, joka muodostaa dynaamiseen ohjelmointiin perustuvien lähestymistapojen perustan geometrisessa pakkauksessa ja riippumattoman joukon ongelmissa. Osoitamme, että jokainen instanssi sisältää guillotine-eroteltavan osajoukon, joka säilyttää vakio-osuuden kokonaispainosta. Tämä parantaa aiempia tuloksia painotetussa tapauksessa ja tuottaa selkeän vakio-kertoimisen approksimaatiokehyksen. Toinen osa keskittyy geometrisiin kaksiosaisiin graafeihin, joissa särmät määrittyvät kahden geometrisen objektiperheen välisten leikkausten tai sisältymisten perusteella. Johdamme lähes tiukat Zarankiewicz-rajat useille luonnollisille leikkausbigraafiluokille, mukaan lukien matalan Ferrers-dimension graafit, segmentti--säde-graafit sekä ruudukon leikkausgraafit. Tulokset paljastavat selkeitä eroja mataladimensionaalisten geometrialuokkien välillä ja osoittavat, kuinka geometriset rajoitteet perustavanlaatuisesti rajoittavat särmätiheyttä samalla kun suuret biklikit vältetään. Kolmas osa tarkastelee maksimaalisen tasapainoisen biklikin ongelmaa kaksiosaisena analogiana täydellisten graafien teorialle. Esittelemme käsitteet ristiväritys ja bi-perfektiys sekä osoitamme, että useat geometriset kaksiosaiset luokat ovat lähes bi-perfektejä. Tämä johtaa vakio-kertoimisiin approksimaatioalgoritmeihin semidefiniittisten ohjelmointirelaksaatioiden avulla. Lopuksi annamme ns. freeable-matriisikarakterisaation kaksiosaisille graafeille, joiden Ferrers-dimensio on kolme. Osoitamme, että tämä luokka voidaan kuvata täsmällisesti kahden äärellisen matriisikuviokiellon avulla. Tämä tuottaa puhtaasti kombinatorisen tunnistuskehyksen, joka ei riipu geometrisista esityksistä. Yhteenvetona väitöskirja kehittää yhtenäisen näkökulman, jossa geometria tuottaa rakenteellista harvuutta ja kuviorajoitteita, mahdollistaen uusia ekstremaalisia tuloksia sekä algoritmisia työkaluja biklikkiongelmiin kaksiosaisissa leikkausgraafeissa."],"dc:format.mimetype":["application/pdf"],"dc:identifier.uri":["https://aaltodoc.aalto.fi/handle/123456789/144483"],"dc:language.iso":["en"],"dc:publisher":["Aalto University","Aalto-yliopisto"],"dc:title":["Extremal and Algorithmic Results for Bipartite Graphs via Ferrers Dimension and Axis-Parallel Geometry","Ekstremaalisia ja algoritmisia tuloksia bipartite-graafeista Ferrers-dimension ja axis-parallel -geometrian kautta"],"dc:type":["G5 Artikkeliväitöskirja"],"dc:type.dcmitype":["text"]},"updated_at":"2026-08-21T22:21:56Z"}