Succinct Data Structure for Path Graphs

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 nlog n+o(nlog n) bits while answering adjacency query in O(log n) time, and neighborhood and degree queries in O(dlog2n) 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(nlog2n) bits while answering adjacency and degree queries in constant time and neighborhood query in O(dlog 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.