Succinct Data Structure for Graphs with d-Dimensional t-Representation

Erdős and West (Discrete Mathematics'85) considered the class of n vertex intersection graphs which have a d-dimensional t-representation (also called a t, d −intersection 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 + 1{2}) d n - (n - 1{2}) d (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 Gₓ, ₃. We address the problem of designing a succinct data structure for the class Gₓ, ₃ in an attempt to generalize the relatively recent results on succinct data structures for interval graphs (Algorithmica'21). Let GₜandGd be the class of graphs with bounded interval number and bounded boxicity obtained by setting d = 1 and t = 1 in Gₓ, ₃, respectively. We have the following results: