The number of disk graphs

Abstract

A disk graph is the intersection graph of disks in the plane, and a unit disk graph is the intersection graph of unit radius disks in the plane. We give upper and lower bounds on the number of labeled unit disk and disk graphs on nn vertices. We show that the number of unit disk graphs on nn vertices is n2n⋅α(n)nn2n⋅α(n)n and the number of disk graphs on nn vertices is n3n⋅β(n)nn3n⋅β(n)n, where α(n)α(n) and β(n)β(n) are Θ(1)Θ(1). We conjecture that there exist constants α,βα,β such that the number of unit disk graphs is n2n⋅(α+o(1))nn2n⋅(α+o(1))n and the number of disk graphs is n3n⋅(β+o(1))nn3n⋅(β+o(1))n.