Browsing Computer Science by Supervisor "Biedl, Therese"
Now showing items 1-9 of 9
-
A 2-Approximation for the Height of Maximal Outerplanar Graph Drawings
(University of Waterloo, 2016-08-18)In this thesis, we study drawings of maximal outerplanar graphs that place vertices on integer coordinates. We introduce a new class of graphs, called umbrellas, and a new method of splitting maximal outerplanar graphs ... -
Area-Efficient Drawings of Outer-1-Planar Graphs
(University of Waterloo, 2020-09-29)We study area-efficient drawings of planar graphs: embeddings of graphs on an integer grid so that the bounding box of the drawing is minimized. Our focus is on the class of outer-1-planar graphs: the family of planar ... -
Bounds on Maximum Matchings in 1-Planar Graphs
(University of Waterloo, 2019-01-29)In this thesis, we study lower bounds on maximum matchings in 1-planar graphs. We expand upon the tools used for proofs of matching bounds in other classes of graphs as well as some original ideas in order to find these ... -
Building a larger class of graphs for efficient reconfiguration of vertex colouring
(University of Waterloo, 2020-05-13)A $k$-colouring of a graph $G$ is an assignment of at most $k$ colours to the vertices of $G$ so that adjacent vertices are assigned different colours. The reconfiguration graph of the $k$-colourings, $\mathcal{R}_k(G)$, ... -
Graph Morphing via Orthogonal Box Drawings
(University of Waterloo, 2023-12-18)Abstract: A graph is a set of vertices, with some pairwise connections given by a set of edges. A graph drawing, such as a node-link diagram, visualizes a graph with geometric features. One of the most common forms of a ... -
List Coloring Some Classes of 1-Planar Graphs
(University of Waterloo, 2021-12-23)In list coloring we are given a graph G and a list assignment for G which assigns to each vertex of G a list of possible colors. We wish to find a coloring of the vertices of G such that each vertex uses a color from its ... -
Restricted String Representations
(University of Waterloo, 2017-08-29)A string representation of a graph assigns to every vertex a curve in the plane so that two curves intersect if and only if the represented vertices are adjacent. This work investigates string representations of graphs ... -
Testing vertex connectivity of bowtie 1-plane graphs
(University of Waterloo, 2022-07-18)A separating set of a connected graph $G$ is a set of vertices $S$ such that $G-S$ is disconnected. $S$ is a minimum separating set of $G$ if there is no separating set of $G$ with fewer vertices than $S$. The size of a ... -
Upward Octagonal Drawings of Ternary Trees
(University of Waterloo, 2016-09-08)We explore ways to embed a ternary tree in an integer coordinate grid such that the width of the drawing is minimized. We provide upper and lower bounds on the width requirement of planar, straight-line, upward, order-preserving ...