License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FUN.2016.16
URN: urn:nbn:de:0030-drops-58671
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5867/
Evans, William ;
van Garderen, Mereke ;
Löffler, Maarten ;
Polishchuk, Valentin
Recognizing a DOG is Hard, But Not When It is Thin and Unit
Abstract
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.
BibTeX - Entry
@InProceedings{evans_et_al:LIPIcs:2016:5867,
author = {William Evans and Mereke van Garderen and Maarten L{\"o}ffler and Valentin Polishchuk},
title = {{Recognizing a DOG is Hard, But Not When It is Thin and Unit}},
booktitle = {8th International Conference on Fun with Algorithms (FUN 2016)},
pages = {16:1--16:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-005-7},
ISSN = {1868-8969},
year = {2016},
volume = {49},
editor = {Erik D. Demaine and Fabrizio Grandoni},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5867},
URN = {urn:nbn:de:0030-drops-58671},
doi = {10.4230/LIPIcs.FUN.2016.16},
annote = {Keywords: graph drawing, planar graphs, disk intersection graphs}
}
Keywords: |
|
graph drawing, planar graphs, disk intersection graphs |
Collection: |
|
8th International Conference on Fun with Algorithms (FUN 2016) |
Issue Date: |
|
2016 |
Date of publication: |
|
02.06.2016 |