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

Lade...
Vorschaubild
Dateien
Zu diesem Dokument gibt es keine Dateien.
Datum
2016
Autor:innen
Evans, William
Löffler, Maarten
Polishchuk, Valentin
Herausgeber:innen
Kontakt
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
URI (zitierfähiger Link)
ArXiv-ID
Internationale Patentnummer
Angaben zur Forschungsförderung
European Union (EU): 319209
Projekt
NEXUS 1492
Open Access-Veröffentlichung
Core Facility der Universität Konstanz
Gesperrt bis
Titel in einer weiteren Sprache
Publikationstyp
Beitrag zu einem Konferenzband
Publikationsstatus
Published
Erschienen in
DEMAINE, Erik D., ed., Fabrizio GRANDONI, ed.. 8th International Conference on Fun with Algorithms (FUN 2016). Leibniz: Wadern : Schloss Dagstuhl, 2016, pp. 16:1-16:12. LIPIcs : Leibniz International Proceedings in Informatics. 49. ISBN 978-3-95977-005-7. Available under: doi: 10.4230/LIPIcs.FUN.2016.16
Zusammenfassung

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

Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
004 Informatik
Schlagwörter
graph drawing, planar graphs, disk intersection graphs
Konferenz
8th International Conference on Fun with Algorithms (FUN 2016), 8. Juni 2016 - 10. Juni 2016, La Maddalena, Italy
Rezension
undefined / . - undefined, undefined
Forschungsvorhaben
Organisationseinheiten
Zeitschriftenheft
Datensätze
Zitieren
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, 8. Juni 2016 - 10. Juni 2016. In: DEMAINE, Erik D., ed., Fabrizio GRANDONI, ed.. 8th International Conference on Fun with Algorithms (FUN 2016). Leibniz: Wadern : Schloss Dagstuhl, 2016, pp. 16:1-16:12. LIPIcs : Leibniz International Proceedings in Informatics. 49. 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>
Interner Vermerk
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Kontakt
Prüfdatum der URL
2019-01-23
Prüfungsdatum der Dissertation
Finanzierungsart
Kommentar zur Publikation
Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Begutachtet
Diese Publikation teilen