Recognizing a DOG is Hard, But Not When It is Thin and Unit
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
Editors
Journal ISSN
Electronic ISSN
ISBN
Bibliographical data
Publisher
Series
DOI (citable link)
International patent number
Link to the license
oops
EU project number
319209
Project
NEXUS 1492
Open Access publication
Collections
Title in another language
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 690
EVANS, 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.16BibTex
@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
URL of original publication
Test date of URL
2019-01-23