Puzzling Grid Embeddings

Cite This

Files in this item

Files Size Format View

There are no files associated with this item.

BECK, Moritz, Sabine STORANDT, 2020. Puzzling Grid Embeddings. Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX 20). Salt Lake City, Utah, USA, Jan 5, 2020 - Jan 6, 2020. In: BLELLOCH, Guy, ed., Irene FINOCCHI, ed.. 2020 Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX). Philadelphia:SIAM, pp. 94-105. ISBN 978-1-61197-600-7. Available under: doi: 10.1137/1.9781611976007.8

@inproceedings{Beck2020-12-17Puzzl-48882, title={Puzzling Grid Embeddings}, year={2020}, doi={10.1137/1.9781611976007.8}, isbn={978-1-61197-600-7}, address={Philadelphia}, publisher={SIAM}, 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 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/rdf/resource/123456789/48882"> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <dc:language>eng</dc:language> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dcterms:issued>2020-12-17</dcterms:issued> <dc:creator>Storandt, Sabine</dc:creator> <dc:contributor>Beck, Moritz</dc:contributor> <dcterms:title>Puzzling Grid Embeddings</dcterms:title> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2020-03-02T10:40:30Z</dcterms:available> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/48882"/> <dc:creator>Beck, Moritz</dc:creator> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2020-03-02T10:40:30Z</dc:date> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <dc:contributor>Storandt, Sabine</dc:contributor> <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> </rdf:Description> </rdf:RDF>

This item appears in the following Collection(s)

Search KOPS


My Account