4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ For planar graphs, there are asymptotics here: dmtcs.org/dmtcs-ojs/index.php/proceedings/article/viewFile/… $\endgroup$ – Louis May 13 '14 at 18:38
  • $\begingroup$ The thing with asymptotics is that if we only know that there are $O(f(n, m))$ planar graphs on $n$ vertices and $m$ edges, then we can only deduce that we will require $O(OPT)$ bits (for an appropriate value of $OPT$). This is what is known as a "compact data structure" instead of a succinct one, which required $OPT + o(OPT)$ bits (i.e leading term of 1). So one does need to be careful. I will take a closer look though and see if anything can be extrapolated. $\endgroup$ – user340082710 May 13 '14 at 19:09
  • $\begingroup$ The question I am trying to ask is: How does one create a succinct data structure for these types of graph classes when it isn't clear what $OPT$ is. Generally, we simply count the number of such objects then take the log, but when we cannot seem to count them... what are some other techniques that one could use? (Planar graphs and partial k-trees are some examples that I am currently looking at where such problems seem to arise). $\endgroup$ – user340082710 May 14 '14 at 16:13
  • 1
    $\begingroup$ it is actually probably an open/difficult problem in complexity theory to determine/prove tight lower bounds on minimum bits required of misc graph classes (& wouldnt be surprised if its connected to other deep connections in the theory such as open complexity class separations). dont think "succinct" actually has a strict technical defn in CS as you seem to write out. in practice/applications there are many basic/standard graph representations that are used to represent graphs regardless of graph class. $\endgroup$ – vzn May 14 '14 at 19:49
  • 3
    $\begingroup$ @ZacharyFrenette Actually, if there are $O(f(n,m))$ planar graphs then the optimal number of bits is $\log_2 f(n,m) + O(1)$, which is probably good enough for you. $\endgroup$ – Yuval Filmus May 15 '14 at 3:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.