10.20381/RUOR-24581
Yelle, Céline
Stack Number, Track Number, and Layered Pathwidth
Université d'Ottawa / University of Ottawa
2020
graph layout
stack layout
stack number
book embedding
page number
track layout
track number
layered path decomposition
layered pathwidth
My University
My University
2020-04-09
2020-04-09
2020-04-09
en
http://hdl.handle.net/10393/40348
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]).