In this talk, I will present a succinct data structure for the class of path graphs (which are a proper subclass of chordal graphs and a proper superclass of interval graphs) with n vertices that support degree, adjacency, and neighborhood queries efficiently. This succinct data structure occupies n log n+o(n log n) bits and answers adjacency query in O(log n) time, and neighborhood and degree queries in O(d log^2 n) time where d is the degree of the queried vertex. I will also discuss a second data structure that answers adjacency queries faster at the expense of slightly more space. More specifically, it's a space-efficient data structure that takes O(n log^2 n) bits and supports adjacency and degree queries in O(1) time, and the neighborhood query in O(d) time where d is the degree of the queried vertex. Central to both these data structures is the usage of the classical heavy path decomposition, followed by careful bookkeeping using an orthogonal range search data structure.

Please email for a
Zoom link