Grid Minors and Products

Notice brève
dc.contributor.authorWorley, David
dc.contributor.supervisorDujmovic, Vida
dc.contributor.supervisorMorin, Pat
dc.date.accessioned2025-09-08T19:57:55Z
dc.date.available2025-09-08T19:57:55Z
dc.date.issued2025-09-08
dc.description.abstractMotivated by recent developments regarding the product structure of planar graphs, we study relationships between treewidth, grid minors, and graph products. We show that the Cartesian product of any two graphs, each connected and each having n vertices, contains an Ω(√n) × Ω(√n) grid minor. This result is tight: the lexicographic product (which includes the Cartesian product as a subgraph) of a star and any n-vertex tree has no ω(√n) × ω(√n) grid minor.
dc.identifier.urihttp://hdl.handle.net/10393/50837
dc.identifier.urihttps://doi.org/10.20381/ruor-31376
dc.language.isoen
dc.publisherUniversité d'Ottawa / University of Ottawa
dc.rightsAttribution-NonCommercial 4.0 Internationalen
dc.rights.urihttp://creativecommons.org/licenses/by-nc/4.0/
dc.subjectDiscrete Mathematics
dc.subjectGraph Theory
dc.subjectGraph Minors
dc.subjectGrid Graphs
dc.subjectGraph Products
dc.subjectTreewidth
dc.titleGrid Minors and Products
dc.typeThesisen
thesis.degree.disciplineGénie / Engineering
thesis.degree.levelMasters
thesis.degree.nameMCS
uottawa.departmentScience informatique et génie électrique / Electrical Engineering and Computer Science

Fichiers

Trousse originale

Voici les éléments 1 - 1 sur 1
Vignette d'image
Nom:
Worley_David_2025_thesis.pdf
Taille:
908.32 KB
Format:
Adobe Portable Document Format
Télécharger

Trousse de licence

Voici les éléments 1 - 1 sur 1
Vignette d'image
Nom:
license.txt
Taille:
6.65 KB
Format:
Item-specific license agreed upon to submission
Description:
Télécharger

Collections

- Thèses, 2011 - // Theses, 2011 -