Publikation:

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

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)
DOI (zitierfähiger Link)
https://doi.org/10.4230/LIPIcs.FUN.2016.16
ArXiv-ID

Internationale Patentnummer

Angaben zur Forschungsförderung

European Union (EU): 319209

Projekt

NEXUS 1492
Open Access-Veröffentlichung

Sammlungen

Informatik und Informationswissenschaft: Publikationen
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

Zugehörige Datensätze in KOPS

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
URL der Originalveröffentl.
http://drops.dagstuhl.de/opus/volltexte/2016/5867/

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