The number of disk graphs.

Journal article

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 n {dot operator} α (n) and the number of disk graphs on n vertices is n {dot operator} β (n), where α (n) and β (n) are Θ (1). We conjecture that there exist constants α, β such that the number of unit disk graphs is n {dot operator} (α + o (1)) and the number of disk graphs is n {dot operator} (β + o (1)). © 2013 Elsevier Ltd.

Authors: McDiarmid, C; Müller, T

• Publication status: Published
• Journal: Eur. J. Comb.
• Volume: 35
• Pages: 413-431
• Publication date: 2014-01-01
• DOI: 10.1016/j.ejc.2013.06.037
• ISSN: 0195-6698