Article ID Journal Published Year Pages File Type
6424238 European Journal of Combinatorics 2014 19 Pages PDF
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 n vertices. We show that the number of unit disk graphs on n vertices is n2n⋅α(n)n and the number of disk graphs on n vertices is n3n⋅β(n)n, where α(n) and β(n) are Θ(1). We conjecture that there exist constants α,β such that the number of unit disk graphs is n2n⋅(α+o(1))n and the number of disk graphs is n3n⋅(β+o(1))n.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,