Succinct Data Structure for Path Graphs
Girish Balakrishnan, N. S. Narayanaswamy, Sankardeep Chakraborty, Kunihiko Sadakane · 2022
We consider the problem of designing space-efficient data structures for unlabelled path graphs with$n$vertices while supporting basic navigational queries such as degree, adjacency, and neighborhood queries efficiently. We provide two solutions for this problem. Our first data structure is succinct and occupies$n\log n+o(n\log n)$bits while answering 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. Our second data structure answers all these queries faster at the expense of slightly more space. More specifically, it consumes$O(n\log^{2}n)$bits while answering adjacency and degree queries in constant time and neighborhood query in$O(d\log n)$time. Central to our data structures is the usage of the classical heavy path decomposition, followed by a careful bookkeeping using an orthogonal range search data structure among others, which may be of independent interest for designing succinct data structures for other graphs.