Succinct Data Structure for Chordal Graphs with Bounded Vertex Leafage

Chordal graphs is a well-studied large graph class that is also a strict super-class of path graphs. Munro and Wu (ISAAC 2018) have given an (n2/4+o(n2))−bit succinct representation for n−vertex unlabeled chordal graphs. A chordal graph G = (V, E) is the intersection graph of sub-trees of a tree T. Based on this characterization, the two parameters of chordal graphs which we consider in this work are leafage, introduced by Lin, McKee and West (Discussiones Mathematicae Graph Theory 1998) and vertex leafage, introduced by Chaplick and Stacho (Discret. Appl. Math. 2014). Leafage is the minimum number of leaves in any possible tree T characterizing G. Let L(u) denote the number of leaves of the sub-tree in T corresponding to u ∈ V and k = max L(u). The smallest k for which there exists a tree T for G is called its vertex leafage. u∈V In this work, 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(nc), c > 0, we obtain a lower bound of ((k−1)nlog n−knlog 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 and k > 1 in o(nc), c > 0, we present a ((k − 1)nlog n + o(knlog n))−bit succinct data structure, constructed using the succinct data structure for path graphs with (k − 1)n vertices. Our data structure supports adjacency query in O(klog n) time and using additional 2nlog n bits, an O(k2dv log n + log2 n) time neighbourhood query where dv is degree of v ∈ V .