Stack Number, Track Number, and Layered Pathwidth
| dc.contributor.author | Yelle, Céline | |
| dc.contributor.supervisor | Dujmovic, Vida | |
| dc.contributor.supervisor | Morin, Pat | |
| dc.date.accessioned | 2020-04-09T18:57:34Z | |
| dc.date.available | 2020-04-09T18:57:34Z | |
| dc.date.issued | 2020-04-09 | en_US |
| dc.description.abstract | In this thesis, we consider three parameters associated with graphs : stack number, track number, and layered pathwidth. Our first result is to show that the stack number of any graph is at most 4 times its layered pathwidth. This result complements an existing result of Dujmovic et al. that showed that the queue number of a graph is at most 3 times its layered pathwidth minus one (Dujmovic, Morin, and Wood [SIAM J. Comput., 553–579, 2005]). Our second result is to show that graphs of track number at most 3 have layered pathwidth at most 4. This answers an open question posed by Banister et al. (Bannister, Devanny, Dujmovic, Eppstein, and Wood [GD 2016, 499–510, 2016, Algorithmica, 1–23, 2018]). | en_US |
| dc.identifier.uri | http://hdl.handle.net/10393/40348 | |
| dc.identifier.uri | http://dx.doi.org/10.20381/ruor-24581 | |
| dc.language.iso | en | en_US |
| dc.publisher | Université d'Ottawa / University of Ottawa | en_US |
| dc.subject | graph layout | en_US |
| dc.subject | stack layout | en_US |
| dc.subject | stack number | en_US |
| dc.subject | book embedding | en_US |
| dc.subject | page number | en_US |
| dc.subject | track layout | en_US |
| dc.subject | track number | en_US |
| dc.subject | layered path decomposition | en_US |
| dc.subject | layered pathwidth | en_US |
| dc.title | Stack Number, Track Number, and Layered Pathwidth | en_US |
| dc.type | Thesis | en_US |
| thesis.degree.discipline | Génie / Engineering | en_US |
| thesis.degree.level | Masters | en_US |
| thesis.degree.name | MCS | en_US |
| uottawa.department | Science informatique et génie électrique / Electrical Engineering and Computer Science | en_US |
