1 Search Results for "van Garderen, Mereke"

Document
DOI: 10.4230/LIPIcs.FUN.2016.16
Recognizing a DOG is Hard, But Not When It is Thin and Unit

Authors: William Evans, Mereke van Garderen, Maarten Löffler, and Valentin Polishchuk

Published in: LIPIcs, Volume 49, 8th International Conference on Fun with Algorithms (FUN 2016)

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.
Cite as

William Evans, Mereke van Garderen, Maarten Löffler, and Valentin Polishchuk. Recognizing a DOG is Hard, But Not When It is Thin and Unit. In 8th International Conference on Fun with Algorithms (FUN 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 49, pp. 16:1-16:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{evans_et_al:LIPIcs.FUN.2016.16,
  author =	{Evans, William and van Garderen, Mereke and L\"{o}ffler, Maarten and Polishchuk, Valentin},
  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 =	{Demaine, Erik D. and Grandoni, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2016.16},
  URN =		{urn:nbn:de:0030-drops-58671},
  doi =		{10.4230/LIPIcs.FUN.2016.16},
  annote =	{Keywords: graph drawing, planar graphs, disk intersection graphs}
}
  • Refine by Author
  • 1 Evans, William
  • 1 Löffler, Maarten
  • 1 Polishchuk, Valentin
  • 1 van Garderen, Mereke

  • Refine by Classification

  • Refine by Keyword
  • 1 disk intersection graphs
  • 1 graph drawing
  • 1 planar graphs

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2016

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact