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 $(n^2/4+o(n^2))-$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 \textit{leafage}, introduced by Lin, McKee and West (Discussiones Mathematicae Graph Theory 1998) and \textit{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 \in V$ and $k=\max\limits_{u \in V} L(u)$. The smallest $k$ for which there exists a tree $T$ for $G$ is called its vertex leafage. In this work, we improve the worst-case information theoretic lower bound of Munro and Wu (ISAAC 2018) for 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>1$ 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 $k>1$ in $o(n/\log n)$, we present a $((k-1)n \log n + o(kn \log n))-$bit 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$.
翻译:暂无翻译