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 $\left( {2nt + \frac{1}{2}} \right)d\log n - \left( {n - \frac{1}{2}} \right)d\log (4\pi 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). Let ${\mathcal{G}_t}{\text{and}}{\mathcal{G}_d}$ be the class of graphs with bounded interval number and bounded boxicity obtained by setting d = 1 and t = 1 in ${\mathcal{G}_{t,d}}$ , respectively. We have the following results:

Given a string S over an alphabet of size $\sigma$, we consider practical implementations of extended compressed RAM on S, which supports access, replace, lnsert, and delete operations on S while maintaining S in compressed form. In this paper, we proposed two implementations where each of them is based on the compressed RAM of Jansson et al. [ICALP 2012], and Grossi et al. [ICALP 2013], respectively. Experimental results show that our implementations support the operations efficiently while keeping the space proportional to the entropy of the input during the updates.

In this paper we initiate the study of designing parameterized compact data structures for interval graph$G$. First, we show that when the maximum degree of$G$is bounded by$\ell$, there exists an$(n\log_{2}\ell+O(n))$-bit data structure while supporting the standard navigational queries i.e., degree, adjacency, and neighborhood optimally. Our data structure takes less space than the information-theoretic lower bound when$\ell\ =\ O(n^{\epsilon})$where$0 < \epsilon < 1$. Furthermore, we show that the space requirement of our data structure is almost optimal by giving an explicit$(\frac{1}{6}n\log_{2}\ell-O(n))$-bit counting lower bound. Thus, we provide a compact representation of interval graphs with bounded degree for the first time in literature. Finally, we consider the interval graphs with bounded chromatic number$(\Delta)$, and design a$(\Delta- 1)n+o(\Delta n)$bit data structure with efficient query times for such graphs. This improves the worst-case information-theoretic lower bound when$\Delta=o(\log n)$.

We consider the problem of designing succinct encodings for some intersection graphs on a circle, which include graph classes such as circle graphs, k-polygon-circle graphs, circle-trapezoid graphs among others. More specifically, we first prove a general counting lower bound, which is of independent interest, for these intersection graph classes, and then present a uniform encoding approach that lets us obtain matching lower and upper bounds for their succinct representation.

Clique-width is a well-studied graph parameter owing to its use in understanding algorithmic tractability. In this paper we design a succinct data structure for graphs on$n$vertices whose clique-width is at most$k \leq \epsilon \sqrt{\log n / \log \log n}$for some constant$0<\epsilon<1$, along with supporting degree, adjacency, neighborhood queries efficiently. This resolves an open problem of Kamali (Algorithmica-2018).

We consider practical implementations of compressed bit vectors, which support rank and select operations on a given bit-string, while storing thebit-string in compressed form. Our approach relies on variable-to-fixed (V2F) encodings of the bit-string, an approach that has not yet been considered systematically for practical encodings of bit-vectors. This approach leadsto fast practical implementations with low redundancy (i.e., the space used by the bit vector in addition to the compressed representation of the bit-string),and is a flexible and promising solution to the problem of supporting rank and select on moderately compressible bit-strings, such as those frequently found in real-world applications.