  We spot a hole in the area of succinct data structures for graph classes from
a universe of size at most $n^n$. Very often, the input graph is labeled by the
user in an arbitrary and easy-to-use way, and the data structure for the graph
relabels the input graph in some way. For any access, the user needs to store
these labels or compute the new labels in an online manner. This might require
more bits than the information-theoretic minimum of the original graph class,
hence, defeating the purpose of succinctness. Given this, the data structure
designer must allow the user to access the data structure with the original
labels, i.e., relabeling is not allowed. We call such a graph data structure
``accessible''. In this paper, we study the complexity of such accessible data
structures for interval graphs, a graph class with information-theoretic
minimum less than $n\log n$ bits.
  - We formalize the concept of "accessibility" (which was implicitly assumed),
and propose the "universal interval representation", for interval graphs.
  - Any data structure for interval graphs in universal interval
representation, which supports both adjacency and degree query simultaneously
with time cost $t_1$ and $t_2$ respectively, must consume at least
$\log_2(n!)+n/(\log n)^{O(t_1+t_2)}$ bits of space. This is also the first
lower bound for graph classes with information-theoretic minimum less than
$n\log_2n$ bits.
  - We provide efficient succinct data structures for interval graphs in
universal interval representation supporting adjacency query and degree query
individually in constant time and space costs. Therefore, two upper bounds
together with the lower bound show that the two elementary queries for interval
graphs are incompatible with each other in the context of succinct data
structure. To the best of our knowledge, this is the first proof of such
incompatibility phenomenon.
