| Title | : | Succinct Data Structure for Graphs with d-Dimensional t-Representation |
| Speaker | : | Girish Balakrishnan (IITM) |
| Details | : | Mon, 4 Mar, 2024 11:00 AM @ SSB-334 |
| Abstract: | : | Erdos and West (Discrete Mathematics'85) considered the class of n vertex intersection graphs which have a d-dimensional t-representation, that is, each vertex of a graph in the class has an associated set consisting of at most t d-dimensional axis-parallel boxes. In particular, for a graph G and for each d ≥ 1, they consider i_d(G) to be the minimum t for which G has such a representation. For fixed t and d, they consider the class of n vertex labeled graphs for which i_d(G) ≤ t, and prove an upper bound of (2nt+½)d log n - (n - ½)d log(4π t) on the logarithm of size of the class.
In this work, for fixed t and d we consider the class of n vertex unlabeled graphs which have a d-dimensional t-representation, denoted by mathcal{G}_{t,d}. We address the problem of designing a succinct data structure for the class mathcal{G}_{t,d} in an attempt to generalize the relatively recent results on succinct data structures for interval graphs (Algorithmica'21). To this end, for each n such that td^2 is in o(n / log n), we first prove a lower bound of (2dt-1)n log n - O(ndt log log n)-bits on the size of any data structure for encoding an arbitrary graph that belongs to mathcal{G}_{t,d}.
We then present a ((2dt-1)n log n + dtlog t + o(ndt log n))-bit data structure for mathcal{G}_{t,d} that supports navigational queries efficiently. Contrasting this data structure with our lower bound argument, we show that for each fixed t and d, and for all n ≥ 0 when td^2 is in o(n/log n) our data structure for mathcal{G}_{t,d} is succinct.
As a byproduct, we also obtain succinct data structures for graphs of bounded boxicity (denoted by d and t = 1) and graphs of bounded interval number (denoted by t and d=1) when td^2 is in o(n/log n). Web Conference Link : meet.google.com/dzj-nekm-tcc |
