We enhance space efficient representations of two types of intersection graphs. We refine the data structure for path graphs of Balakrishnan et al. to give a succinct data structure of n log n + o(n log n) bits that supports adjacency test, degree and neighbourhood queries in $O\left( {\frac{{\log n}}{{\log \log n}}} \right)$ time (for neighbourhood queries, this is the amount of time for each neighbour reported). To achieve O(1) query times, we give a data structure using (3 + ε)n log n + o(n log n) bits for any constant ε > 0. Furthermore, we are able to support both the distance and shortest path queries on unweighted path graphs using (2 + ε)n log n+ o(n log n) bits in O(log n/ log log n) time (shortest path uses an additional O(1) time per vertex on the path). This is the first compact distance oracles for path graphs. Turning to chordal graphs, we enhance the succinct data structure of Munro and Wu to reduce all query times including performing adjacency test in O(1) time.

An interval graph is the intersection graph of intervals on the real line. We consider the problem of constructing space efficient data structures for two subclasses of interval graphs: those with maximum degree σ1and those with chromatic number at most σ2.We show that both bounded degree and bounded chromatic number interval graphs have a tight lower bound of n lg σi− o(n lg σi) bits (i = 1, 2). This improves the lower bound of Chakraborty and Jo from $\frac{1}{6}n\lg {\sigma _i} - O(n)$. For bounded chromatic number interval graphs, we give the first succinct data structure occupying n lg σ2+ O(n) bits that supports navigational operations and distance queries in O(σ2lgn) time. To match Chakraborty and Jo’s time complexity of O(lg lg σ2), which uses (σ2− 1)n+O(n) bits, we use 2nlgσ2+O(n) bits instead.