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:

We consider the problem of designing space-efficient data structures for unlabelled path graphs with$n$vertices while supporting basic navigational queries such as degree, adjacency, and neighborhood queries efficiently. We provide two solutions for this problem. Our first data structure is succinct and occupies$n\log n+o(n\log n)$bits while answering adjacency query in$O(\log n)$time, and neighborhood and degree queries in$O(d\log^{2}n)$time where$d$is the degree of the queried vertex. Our second data structure answers all these queries faster at the expense of slightly more space. More specifically, it consumes$O(n\log^{2}n)$bits while answering adjacency and degree queries in constant time and neighborhood query in$O(d\log n)$time. Central to our data structures is the usage of the classical heavy path decomposition, followed by a careful bookkeeping using an orthogonal range search data structure among others, which may be of independent interest for designing succinct data structures for other graphs.

Depth-first search (DFS) is a very well-known graph traversal method which confers a number of structural properties that causes DFS to have numerous applications. These properties are captured in the DFS tree (forest), and are used to design efficient algorithms for many basic and fundamental algorithmic graph problems, namely, biconnectivity, 2-edge connectivity, topological sorting and planarity testing among many others. Recently, Chakraborty and Sadakane (MFCS 2019) studied the problem of compactly indexing the lexicographic DFS tree, and they showed various applications of this by designing an efficient index for shortest path, strongly connected component etc. Here, lexicographical means that the DFS algorithm chooses at every step the vertex that is unvisited and smallest in the lexicographical order of the vertices. Chakraborty and Sadakane presented their solution in two well-known models: The indexing and encoding models. In the indexing model, we wish to build an index$I$after preprocessing the input graph$G$such that queries can be answered using both$I$and$G$whereas in the encoding model, we seek to build a data structure$E$after preprocessing$G$such that the following queries have to be answered using only$E, (\mathrm{i})$return true if$t_{1}$is visited before$t_{0}$in the lexicographic DFS tree$T$rooted at$s$, and false otherwise, and (ii) return the number of children of any given node$v\in T$.

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).