I would like to have a bound on the cardinality of the set of unit disk graphs with $N$ vertices. It is known that checking whether a graph is a member of this set is NP-hard. Does this lead to any lower bound on the cardinality, assuming P $\neq$ NP? For example, suppose there is an ordering on all graphs with $N$ vertices. Would NP-hardness then imply the cardinality exceeds $2^N$, in that otherwise you could test for membership in polynomial time by doing a binary search through the set? I think this would assume that you have somehow stored the set in memory... Is this allowed? Defintion: A graph is a unit disk graph if each vertex can be associated with a unit disk in the plane, such that vertices are connected whenever their disks intersect.Here is a reference on NP-hardness of membership testing for unit disk graphs:http://disco.ethz.ch/members/pascal/refs/pos_1998_breu.pdf
Can I bound the cardinality of a set if testing for membership in it is known to be NP-complete?
cc.complexity theory;graph theory
I'm not sure if you're asking this question for the technique or for the answer, but there is a recent paper by McDiarmid and Mueller where they show the number of (labeled) unit-disk graphs on $n$ vertices is $2^{(2 + o(1))n}$; see http://homepages.cwi.nl/~mueller/Papers/countingDGs.pdf .