Recognizing a DOG is Hard, But Not When It is Thin and Unit
William Evans, Mereke van Garderen, Maarten Löffler, Valentin Polishchuk · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2016
We define the notion of disk-obedience for a set of disks in the plane and give results for diskobedient graphs (DOGs), which are disk intersection graphs (DIGs) that admit a planar embedding with vertices inside the corresponding disks. We show that in general it is hard to recognize a DOG, but when the DIG is thin and unit (i.e., when the disks are unit disks), it can be done in linear time.