The number of disk graphs

Tobias Muller, C.J.H. McDiarmid

Research output: Contribution to journalArticleAcademicpeer-review

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.
Original languageEnglish
Pages (from-to)413-431
Number of pages19
JournalEuropean Journal of Combinatorics
Volume35
DOIs
Publication statusPublished - 2014

Fingerprint

Dive into the research topics of 'The number of disk graphs'. Together they form a unique fingerprint.

Cite this