Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6424238 | European Journal of Combinatorics | 2014 | 19 Pages |
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
Colin McDiarmid, Tobias Müller,