Recognizing a DOG is Hard, But Not When It is Thin and Unit

No Thumbnail Available
Files
There are no files associated with this item.
Date
2016
Authors
Evans, William
Löffler, Maarten
Polishchuk, Valentin
Editors
Contact
Journal ISSN
Electronic ISSN
ISBN
Bibliographical data
Publisher
Series
URI (citable link)
DOI (citable link)
ArXiv-ID
International patent number
Link to the license
oops
EU project number
319209
Project
NEXUS 1492
Open Access publication
Restricted until
Title in another language
Research Projects
Organizational Units
Journal Issue
Publication type
Contribution to a conference collection
Publication status
Published
Published in
8th International Conference on Fun with Algorithms (FUN 2016) / Demaine, Erik D.; Grandoni, Fabrizio (ed.). - Leibniz : Wadern : Schloss Dagstuhl, 2016. - (LIPIcs : Leibniz International Proceedings in Informatics ; 49). - pp. 16:1-16:12. - ISBN 978-3-95977-005-7
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
Summary in another language
Subject (DDC)
004 Computer Science
Keywords
graph drawing, planar graphs, disk intersection graphs
Conference
8th International Conference on Fun with Algorithms (FUN 2016), Jun 8, 2016 - Jun 10, 2016, La Maddalena, Italy
Review
undefined / . - undefined, undefined. - (undefined; undefined)
Cite This
ISO 690EVANS, William, Mereke VAN GARDEREN, Maarten LÖFFLER, Valentin POLISHCHUK, 2016. Recognizing a DOG is Hard, But Not When It is Thin and Unit. 8th International Conference on Fun with Algorithms (FUN 2016). La Maddalena, Italy, Jun 8, 2016 - Jun 10, 2016. In: DEMAINE, Erik D., ed., Fabrizio GRANDONI, ed.. 8th International Conference on Fun with Algorithms (FUN 2016). Leibniz:Wadern : Schloss Dagstuhl, pp. 16:1-16:12. ISBN 978-3-95977-005-7. Available under: doi: 10.4230/LIPIcs.FUN.2016.16
BibTex
@inproceedings{Evans2016Recog-44771,
  year={2016},
  doi={10.4230/LIPIcs.FUN.2016.16},
  title={Recognizing a DOG is Hard, But Not When It is Thin and Unit},
  url={http://drops.dagstuhl.de/opus/volltexte/2016/5867/},
  number={49},
  isbn={978-3-95977-005-7},
  publisher={Wadern : Schloss Dagstuhl},
  address={Leibniz},
  series={LIPIcs : Leibniz International Proceedings in Informatics},
  booktitle={8th International Conference on Fun with Algorithms (FUN 2016)},
  pages={16:1--16:12},
  editor={Demaine, Erik D. and Grandoni, Fabrizio},
  author={Evans, William and van Garderen, Mereke and Löffler, Maarten and Polishchuk, Valentin}
}
RDF
<rdf:RDF
    xmlns:dcterms="http://purl.org/dc/terms/"
    xmlns:dc="http://purl.org/dc/elements/1.1/"
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
    xmlns:bibo="http://purl.org/ontology/bibo/"
    xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
    xmlns:foaf="http://xmlns.com/foaf/0.1/"
    xmlns:void="http://rdfs.org/ns/void#"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > 
  <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/44771">
    <dc:creator>Löffler, Maarten</dc:creator>
    <dcterms:title>Recognizing a DOG is Hard, But Not When It is Thin and Unit</dcterms:title>
    <dc:creator>Polishchuk, Valentin</dc:creator>
    <dc:creator>Evans, William</dc:creator>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-01-30T11:29:44Z</dcterms:available>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/44771"/>
    <dc:contributor>van Garderen, Mereke</dc:contributor>
    <dc:creator>van Garderen, Mereke</dc:creator>
    <dc:language>eng</dc:language>
    <dcterms:issued>2016</dcterms:issued>
    <dc:contributor>Löffler, Maarten</dc:contributor>
    <dc:contributor>Evans, William</dc:contributor>
    <dcterms:abstract xml:lang="eng">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</dcterms:abstract>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:contributor>Polishchuk, Valentin</dc:contributor>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-01-30T11:29:44Z</dc:date>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
  </rdf:Description>
</rdf:RDF>
Internal note
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Contact
Test date of URL
2019-01-23
Examination date of dissertation
Method of financing
Comment on publication
Alliance license
Corresponding Authors der Uni Konstanz vorhanden
International Co-Authors
Bibliography of Konstanz
Refereed