  Since Jacobson [FOCS89] initiated the investigation of succinct graph
encodings 35 years ago, there has been a long list of results on balancing the
generality of the class, the speed, the succinctness of the encoding, and the
query support. Let Cn denote the set consisting of the graphs in a class C that
with at most n vertices. A class C is nontrivial if the
information-theoretically min number log |Cn| of bits to distinguish the
members of Cn is Omega(n). An encoding scheme based upon a single class C is
C-opt if it takes a graph G of Cn and produces in deterministic O(n) time an
encoded string of at most log |Cn| + o(log |Cn|) bits from which G can be
recovered in O(n) time. Despite the extensive efforts in the literature, trees
and general graphs were the only nontrivial classes C admitting C-opt encoding
schemes that support the degree query in O(1) time.
  Basing an encoding scheme upon a single class ignores the possibility of a
shorter encoded string using additional properties of the graph input. To
leverage the inherent structures of individual graphs, we propose to base an
encoding scheme upon of multiple classes: An encoding scheme based upon a
family F of classes, accepting all graphs in UF, is F-opt if it is C-opt for
each C in F. Having a C-opt encoding scheme for each C in F does not guarantee
an F-opt encoding scheme. Under this more stringent criterion, we present an
F-opt encoding scheme for a family F of an infinite number of classes such that
UF comprises all graphs of bounded Hadwiger numbers. F consists of the
nontrivial quasi-monotone classes of k-clique-minor-free graphs for each
positive integer k. Our F-opt scheme supports queries of degree, adjacency,
neighbor-listing, and bounded-distance shortest path in O(1) time per output.
We broaden the graph classes admitting opt encoding schemes that also
efficiently support fundamental queries.
