Succinct data structure for path graphs ☆

We consider the problem of designing a succinct data structure for path graphs , that generalizes interval graphs, on n vertices while efficiently supporting degree, adjacency, and neighbourhood queries. We provide the following two solutions for this problem:1. an n log n + o(n log n)-bit succinct data structure that supports adjacency query in O (log n) time, neighbourhood query in O (d log n) time and finally, degree query in min{ O (log2 n), O (d log n)} time where d is the degree of the queried vertex.2. an O (n log2 n)-bit space-efficient data structure that supports adjacency, neighborhood, and degree queries optimally.Central to our data structures is the usage of the heavy path decomposition, followed by careful bookkeeping using an orthogonal range search data structure using wavelet trees among others, which may be of independent interest for designing succinct data structures for other graph classes.(c) 2023 Elsevier Inc. All rights reserved.

Automated summary

This paper addresses the problem of designing a succinct data structure for path graphs and provides two solutions. The first solution supports adjacency, neighbourhood, and degree queries with time complexities of O(log n), O(d log n), and min{O(log2 n), O(d log n)} respectively. The second solution is a space-efficient data structure that optimally supports adjacency, neighbourhood, and degree queries.