Grid Minors and Products
| dc.contributor.author | Worley, David | |
| dc.contributor.supervisor | Dujmovic, Vida | |
| dc.contributor.supervisor | Morin, Pat | |
| dc.date.accessioned | 2025-09-08T19:57:55Z | |
| dc.date.available | 2025-09-08T19:57:55Z | |
| dc.date.issued | 2025-09-08 | |
| dc.description.abstract | Motivated 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.uri | http://hdl.handle.net/10393/50837 | |
| dc.identifier.uri | https://doi.org/10.20381/ruor-31376 | |
| dc.language.iso | en | |
| dc.publisher | Université d'Ottawa / University of Ottawa | |
| dc.rights | Attribution-NonCommercial 4.0 International | en |
| dc.rights.uri | http://creativecommons.org/licenses/by-nc/4.0/ | |
| dc.subject | Discrete Mathematics | |
| dc.subject | Graph Theory | |
| dc.subject | Graph Minors | |
| dc.subject | Grid Graphs | |
| dc.subject | Graph Products | |
| dc.subject | Treewidth | |
| dc.title | Grid Minors and Products | |
| dc.type | Thesis | en |
| thesis.degree.discipline | Génie / Engineering | |
| thesis.degree.level | Masters | |
| thesis.degree.name | MCS | |
| uottawa.department | Science informatique et génie électrique / Electrical Engineering and Computer Science |
