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

I am Girish Balakrishnan, a PhD student at the Indian Institute of Technology Madras and am currently working on the design of succinct data structures for special graph classes. I have around fourteen years of work experience which include seven years as a developer in the IT industry and seven years in teaching. I did my M.S. at the Case Western Reserve University, Cleveland, USA where my interests were Complex Systems and Systems Biology. For more details check my LinkedIn profile.