PhD Defence • Algorithms and Complexity • Succinct and Compact Data Structures for Intersection Graphs

Please note: This PhD defence will take place in DC 1331.

Kaiyu Wu, PhD candidate
David R. Cheriton School of Computer Science

Supervisor: Professor Ian Munro

This thesis designs space efficient data structures for several classes of intersection graphs, including interval graphs, path graphs and chordal graphs. Our goal is to support navigational operations such as adjacent and neighbourhood and distance operations such as distance and shortest path efficiently while occupying optimal space, or a constant factor of the optimal space.

Using our techniques, we first resolve an open problem with regards to succinctly representing ordinal trees that is able to convert between the index of a node in a depth-first traversal (i.e., pre-order) and in a breadth-first traversal (i.e., level-order) of the tree. Using this, we are able to augment previous succinct data structures for interval graphs with the distance operation.

We also study several variations of the data structure problem in interval graphs: beer interval graphs and dynamic interval graphs. In beer interval graphs, we are given that some vertices of the graph are beer nodes (representing beer stores) and we consider only those paths that pass through at least one of these beer nodes. We give data structure results and prove space lower bounds for these graphs. We study dynamic interval graphs under several well known dynamic models such as incremental or offline, and we give data structures for each of these models.

Finally we consider path graphs where we improve on previous works by exploiting orthogonal range reporting data structures. For optimal space representations, we improve the run time of the queries, while for non-optimal space representations (but optimal query times), we reduce the space needed.