2024/02/06 by Balakrishnan, Girish, Chakraborty, Sankardeep, Narayanaswamy, N S +1
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2402.03748
We improve the worst-case information theoretic lower bound of Munro and Wu (ISAAC 2018) for n-vertex unlabeled chordal graphs when vertex leafage is bounded and leafage is unbounded. The class of unlabeled k-vertex leafage chordal graphs that consists of all chordal graphs with vertex leafage at most k and unbounded leafage, denoted Gk, is introduced for the first time. For k>0 in o(n/log n), we obtain a lower bound of ((k-1)n log n -kn log k - O(log n))-bits on the size of any data structure that encodes a graph in Gk. Further, for every k-vertex leafage chordal graph G such that for k>1 in o(nc), c >0, we present a ((k-1)n log n + o(kn log n))-bit succinct data structure, constructed using the succinct data structure for path graphs with kn/2 vertices. Our data structure supports adjacency query in O(k log n) time and using additional 2n log n bits, an O(k2 dv log n + log2 n) time neighbourhood query where dv is degree of v ∈ V.