Recognizing a DOG is Hard but not when it is Thin and Unit

We define the notion of disk-obedience for a set of disks in the plane and give results for disk-obedient 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.

keywords: Computational Geometry, Graph Drawing, Graphs Theory, UDG

Conference Proceedings (peer-reviewed)

Maarten Löffler, Mereke van Garderen, Valentin Polishchuk, Will Evans
Recognizing a DOG is Hard but not when it is Thin and Unit
Proc. 8th International Conference on Fun with Algorithms
LIPIcs, 49, 16:1–16:12, 2016
http://drops.dagstuhl.de/opus/volltexte/2016/5867

back to list