2026-10-12T03:04:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5867 2024-03-06T09:37:06Z ddc:004 open_access

Recognizing a DOG is Hard, But Not When It is Thin and Unit Evans, William van Garderen, Mereke Löffler, Maarten Polishchuk, Valentin graph drawing planar graphs disk intersection graphs 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik William Evans and Mereke van Garderen and Maarten Löffler and Valentin Polishchuk 2016 Is Part Of LIPIcs, Volume 49, 8th International Conference on Fun with Algorithms (FUN 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2016.16 urn:nbn:de:0030-drops-58671 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2016.16 eng https://creativecommons.org/licenses/by/3.0/legalcode