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]).

This PhD thesis is comprised of 3 results in computational geometry and graph theory. In the first paper, I demonstrate that the piercing number of a set S of pairwise intersecting convex shapes in the plane is bounded by O(\alpha(S)), where \alpha(S) is the fatness of the set S, improving upon the previous upper-bound of O(\alpha(S)^2). In the second article, I show that anagram-free vertex colouring of a 2\times n square grid requires a number of colours that increases with n. This answers an open question in Wilson's thesis and shows that even graphs of pathwidth 2 do not have anagram-free colouring with a bounded number of colours. The third article is a study on the geodesic anagram-free chromatic number of chordal and interval graphs. \emph{Geodesic anagram-free chromatic number} is defined as the minimum number of colours required to colour a graph such that all shortest paths between any pair of vertices are coloured anagram-free. In particular, I prove that the geodesic anagram-free chromatic number of a chordal graph G is 32p'w, where p' is the pathwidth of the subtree intersection representation graph (tree) of G, and w is the clique number of G. Additionally, I prove that the geodesic anagram-free chromatic number of an interval graph is bounded by 32p, where p is the pathwidth of the interval graph. This PhD thesis is comprised of 3 results in computational geometry and graph theory.