2026-07-24T18:02:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24266 2025-11-12T13:39:37Z ddc:004 open_access

Succinct Data Structures for Chordal Graph with Bounded Leafage or Vertex Leafage He, Meng Wu, Kaiyu Chordal Graph Leafage Vertex Leafage Succinct Data Structure We improve the recent succinct data structure result of Balakrishnan et al. for chordal graphs with bounded vertex leafage (SWAT 2024). A chordal graph is a widely studied graph class which can be characterized as the intersection graph of subtrees of a host tree, denoted as a tree representation of the chordal graph. The vertex leafage and leafage parameters of a chordal graph deal with the existence of a tree representation with a bounded number of leaves in either the subtrees representing the vertices or the host tree itself. We simplify the lower bound proof of Balakrishnan et al. which applied to only chordal graphs with bounded vertex leafage, and extend it to a lower bound proof for chordal graphs with bounded leafage as well. For both classes of graphs, the information-theoretic lower bound we (re-)obtain for k = o(n) is (k-1)nlog n - knlog k - o(knlog n) bits, where the leafage or vertex leafage of the graph is at most k = o(n). We further extend the range of the parameter k to Θ(n) as well. Then we give a succinct data structure using (k-1)nlog (n/k) + o(knlog n) bits to answer adjacent queries, which test the adjacency between pairs of vertices, in O((log k)/(log log n) + 1) time compared to the O(klog n) time of the data structure of Balakrishnan et al. For the neighborhood query which lists the neighbours of a given vertex, our query time is O((log n)/(log log n)) per neighbour compared to O(k²log n) per neighbour. We also extend the data structure ideas to obtain a succinct data structure for chordal graphs with bounded leafage k, answering an open question of Balakrishnan et al. Our succinct data structure, which uses (k-1)nlog (n/k) + o(knlog n) bits, has query time O(1) for the adjacent query and O(1) per neighbour for the neighborhood query. Using slightly more space (an additional (1+ε)nlog n bits for any ε > 0) allows distance queries, which compute the number of edges in the shortest path between two given vertices, to be answered in O(1) time as well. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Meng He and Kaiyu Wu 2025 Is Part Of LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WADS.2025.35 urn:nbn:de:0030-drops-242660 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.35 eng https://creativecommons.org/licenses/by/4.0/legalcode