Publikation:

Puzzling Grid Embeddings

Lade...
Vorschaubild

Dateien

Zu diesem Dokument gibt es keine Dateien.

Datum

2020

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

Projekt

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

BLELLOCH, Guy, ed., Irene FINOCCHI, ed.. 2020 Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX). Philadelphia: SIAM, 2020, pp. 94-105. ISBN 978-1-61197-600-7. Available under: doi: 10.1137/1.9781611976007.8

Zusammenfassung

We present a pipeline that, given a weighted graph as an input, produces a planar grid embedding where all edges are represented as axis-aligned straight lines with their Euclidean length matching their edge weight (if such an embedding exists). Being able to compute such embeddings is important for visualization purposes but is additionally helpful to solve certain optimization problems faster, as e.g. the Steiner tree problem. Our embedding pipeline consists of three main steps: In the first step, we identify rigid substructures which we call puzzle pieces. In the second step, we merge puzzle pieces if possible. In the third and last step, we compute the final embedding (or decide that such an embedding does not exist) via backtracking. We describe suitable data structures and engineering techniques for accelerating all steps of the pipeline along the way. Experiments on a large variety of input graphs demonstrate the applicability and scalability of our approach.

Zusammenfassung in einer weiteren Sprache

Fachgebiet (DDC)
004 Informatik

Schlagwörter

Konferenz

Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX 20), 5. Jan. 2020 - 6. Jan. 2020, Salt Lake City, Utah, USA
Rezension
undefined / . - undefined, undefined

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Zugehörige Datensätze in KOPS

Zitieren

ISO 690BECK, Moritz, Sabine STORANDT, 2020. Puzzling Grid Embeddings. Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX 20). Salt Lake City, Utah, USA, 5. Jan. 2020 - 6. Jan. 2020. In: BLELLOCH, Guy, ed., Irene FINOCCHI, ed.. 2020 Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX). Philadelphia: SIAM, 2020, pp. 94-105. ISBN 978-1-61197-600-7. Available under: doi: 10.1137/1.9781611976007.8
BibTex
@inproceedings{Beck2020-12-17Puzzl-48882,
  year={2020},
  doi={10.1137/1.9781611976007.8},
  title={Puzzling Grid Embeddings},
  isbn={978-1-61197-600-7},
  publisher={SIAM},
  address={Philadelphia},
  booktitle={2020 Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX)},
  pages={94--105},
  editor={Blelloch, Guy and Finocchi, Irene},
  author={Beck, Moritz and Storandt, Sabine}
}
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/48882">
    <dc:language>eng</dc:language>
    <dc:contributor>Storandt, Sabine</dc:contributor>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dcterms:abstract xml:lang="eng">We present a pipeline that, given a weighted graph as an input, produces a planar grid embedding where all edges are represented as axis-aligned straight lines with their Euclidean length matching their edge weight (if such an embedding exists). Being able to compute such embeddings is important for visualization purposes but is additionally helpful to solve certain optimization problems faster, as e.g. the Steiner tree problem. Our embedding pipeline consists of three main steps: In the first step, we identify rigid substructures which we call puzzle pieces. In the second step, we merge puzzle pieces if possible. In the third and last step, we compute the final embedding (or decide that such an embedding does not exist) via backtracking. We describe suitable data structures and engineering techniques for accelerating all steps of the pipeline along the way. Experiments on a large variety of input graphs demonstrate the applicability and scalability of our approach.</dcterms:abstract>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2020-03-02T10:40:30Z</dc:date>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/48882"/>
    <dc:contributor>Beck, Moritz</dc:contributor>
    <dcterms:issued>2020-12-17</dcterms:issued>
    <dc:creator>Beck, Moritz</dc:creator>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2020-03-02T10:40:30Z</dcterms:available>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:creator>Storandt, Sabine</dc:creator>
    <dcterms:title>Puzzling Grid Embeddings</dcterms:title>
    <dspace:isPartOfCollection 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.

Prüfdatum der URL

Prüfungsdatum der Dissertation

Finanzierungsart

Kommentar zur Publikation

Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Ja
Begutachtet
Diese Publikation teilen