PhD Seminar • Algorithms and Complexity • Succinct Intersection Graphs Revisited

Please note: This PhD seminar will take place in DC 3317.

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

Supervisor: Professor J. Ian Munro

We enhance several data structures for intersection graphs. The data structures of Chakraborty and Jo for bounded degree and bounded chromatic number interval graphs, Balakrishnan et al. We show that both bounded degree and bounded chromatic number interval graphs have a tight lower bound of $n\log \sigma$ (lower order terms omitted) bits where $\sigma$ is the maximum degree or chromatic number of the graph. This improves the lower bound of Chakraborty and Jo from $\frac{1}{6}n\log\sigma$.

For bounded chromatic number interval graphs, we give a $n\log \sigma$ bit space succinct data structure with $O(\sigma\log n)$ query times. To match the time complexity of $O(\log\log\sigma)$ we use $2n\log\sigma$ bits rather than $(\sigma -1)n$ bits.

For path graphs, we give a succinct $n\log n$ bit data structure with query times $O(\frac{\log n}{\log\log n})$ rather than $O(\log^2 n)$ of Balakrishnan et al. To achieve $O(1)$ query times, we give a data structure using $(2+\varepsilon)n\log n$ bits rather than $O(n\log^2 n)$ bits.