Background: I am interested in finding succinct data structures for certain types of graph classes, particularly partial k-trees. For general graphs, there are $\binom{\binom{n}{2}}{m}$ graphs on $n$ vertices and $m$ edges, and so the minimum number of bits required to encode a graph is simply the $\log$ of the amount above. In general, a succinct data structure for a combinatorial object is done in $OPT + o(OPT)$ bits, where $OPT$ denotes the optimal amount of bits required for the encoding.
However, I've found out that this is quite difficult for certain graph classes, such as partial k-trees or planar graphs. Namely, I would like to know, for any $k$, how many partial k-trees on $n$ vertices and $m$ edges are there (and the same goes for planar graphs). The reason I ask is because: how does one know if a data structure representation for a particular graph class is succinct if we do not know how many such graphs there are $n$ vertices and $m$ edges (i.e if we do not know what $OPT$ is)? As far as I can tell, there doesn't seem to be an expression for the number of planar graphs on $n$ vertices and $m$ edges... and there is much less work done for the case of partial k-trees.
