Publikation: Puzzling Grid Embeddings
Dateien
Datum
Autor:innen
Herausgeber:innen
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
DOI (zitierfähiger Link)
Internationale Patentnummer
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Core Facility der Universität Konstanz
Titel in einer weiteren Sprache
Publikationstyp
Publikationsstatus
Erschienen in
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)
Schlagwörter
Konferenz
Rezension
Zitieren
ISO 690
BECK, 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.8BibTex
@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>