Succinct Data Structure for Chordal Graphs with Bounded Vertex Leafage

Abstract

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 ${\mathcal{G}}_k$, 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 ${\mathcal{G}}_k$. Further, for every $k-$vertex leafage chordal graph $G$ such that for $k>1$ in $o(n^c),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(k^2{d}_v\log n+{\log }^{2}n)$ time neighbourhood query where $d_v$ is degree of $v\in V$.

19 pages, 2 figure