Type of Publication: | Contribution to a conference collection |
Publication status: | Published |
URI (citable link): | http://nbn-resolving.de/urn:nbn:de:bsz:352-2-zrihd4nlcfc35 |
Author: | Angelini, Patrizio; Chaplick, Steven; Cornelsen, Sabine; Da Lozzo, Giordano; Roselli, Vincenzo |
Year of publication: | 2019 |
Conference: | 35th International Symposium on Computational Geometry (SoCG 2019), Jun 18, 2019 - Jun 21, 2019, Portland, United States |
Published in: | 35th International Symposium on Computational Geometry (SoCG 2019) / Barequet, Gill; Wang, Yusu (ed.). - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. - (LIPIcs : Leibniz International Proceedings in Informatics ; 129). - eISSN 1868-8969 |
DOI (citable link): | https://dx.doi.org/10.4230/LIPIcs.SoCG.2019.10 |
Summary: |
We consider the problem of morphing between contact representations of a plane graph. In a contact representation of a plane graph, vertices are realized by internally disjoint elements from a family of connected geometric objects. Two such elements touch if and only if their corresponding vertices are adjacent. These touchings also induce the same embedding as in the graph. In a morph between two contact representations we insist that at each time step (continuously throughout the morph) we have a contact representation of the same type. We focus on the case when the geometric objects are triangles that are the lower-right half of axis-parallel rectangles. Such RT-representations exist for every plane graph and right triangles are one of the simplest families of shapes supporting this property. Thus, they provide a natural case to study regarding morphs of contact representations of plane graphs. We study piecewise linear morphs, where each step is a linear morph moving the endpoints of each triangle at constant speed along straight-line trajectories. We provide a polynomial-time algorithm that decides whether there is a piecewise linear morph between two RT-representations of a plane triangulation, and, if so, computes a morph with a quadratic number of linear morphs. As a direct consequence, we obtain that for 4-connected plane triangulations there is a morph between every pair of RT-representations where the ``top-most'' triangle in both representations corresponds to the same vertex. This shows that the realization space of such RT-representations of any 4-connected plane triangulation forms a connected set.
|
Subject (DDC): | 004 Computer Science |
Link to License: | Attribution 4.0 International |
Bibliography of Konstanz: | Yes |
ANGELINI, Patrizio, Steven CHAPLICK, Sabine CORNELSEN, Giordano DA LOZZO, Vincenzo ROSELLI, 2019. Morphing Contact Representations of Graphs. 35th International Symposium on Computational Geometry (SoCG 2019). Portland, United States, Jun 18, 2019 - Jun 21, 2019. In: BAREQUET, Gill, ed., Yusu WANG, ed.. 35th International Symposium on Computational Geometry (SoCG 2019). Wadern:Schloss Dagstuhl - Leibniz-Zentrum für Informatik. eISSN 1868-8969. Available under: doi: 10.4230/LIPIcs.SoCG.2019.10
@inproceedings{Angelini2019Morph-45596, title={Morphing Contact Representations of Graphs}, year={2019}, doi={10.4230/LIPIcs.SoCG.2019.10}, number={129}, address={Wadern}, publisher={Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, series={LIPIcs : Leibniz International Proceedings in Informatics}, booktitle={35th International Symposium on Computational Geometry (SoCG 2019)}, editor={Barequet, Gill and Wang, Yusu}, author={Angelini, Patrizio and Chaplick, Steven and Cornelsen, Sabine and Da Lozzo, Giordano and Roselli, Vincenzo} }
<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/45596"> <dc:contributor>Chaplick, Steven</dc:contributor> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dc:creator>Da Lozzo, Giordano</dc:creator> <dcterms:rights rdf:resource="http://creativecommons.org/licenses/by/4.0/"/> <dc:contributor>Da Lozzo, Giordano</dc:contributor> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-04-05T12:30:58Z</dcterms:available> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-04-05T12:30:58Z</dc:date> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <dc:contributor>Angelini, Patrizio</dc:contributor> <dc:creator>Roselli, Vincenzo</dc:creator> <dc:contributor>Cornelsen, Sabine</dc:contributor> <dc:creator>Cornelsen, Sabine</dc:creator> <dc:language>eng</dc:language> <dcterms:title>Morphing Contact Representations of Graphs</dcterms:title> <dc:rights>Attribution 4.0 International</dc:rights> <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/45596/1/Angelini_2-zrihd4nlcfc35.pdf"/> <dcterms:issued>2019</dcterms:issued> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/45596"/> <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/45596/1/Angelini_2-zrihd4nlcfc35.pdf"/> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dc:creator>Chaplick, Steven</dc:creator> <dc:contributor>Roselli, Vincenzo</dc:contributor> <dcterms:abstract xml:lang="eng">We consider the problem of morphing between contact representations of a plane graph. In a contact representation of a plane graph, vertices are realized by internally disjoint elements from a family of connected geometric objects. Two such elements touch if and only if their corresponding vertices are adjacent. These touchings also induce the same embedding as in the graph. In a morph between two contact representations we insist that at each time step (continuously throughout the morph) we have a contact representation of the same type. We focus on the case when the geometric objects are triangles that are the lower-right half of axis-parallel rectangles. Such RT-representations exist for every plane graph and right triangles are one of the simplest families of shapes supporting this property. Thus, they provide a natural case to study regarding morphs of contact representations of plane graphs. We study piecewise linear morphs, where each step is a linear morph moving the endpoints of each triangle at constant speed along straight-line trajectories. We provide a polynomial-time algorithm that decides whether there is a piecewise linear morph between two RT-representations of a plane triangulation, and, if so, computes a morph with a quadratic number of linear morphs. As a direct consequence, we obtain that for 4-connected plane triangulations there is a morph between every pair of RT-representations where the ``top-most'' triangle in both representations corresponds to the same vertex. This shows that the realization space of such RT-representations of any 4-connected plane triangulation forms a connected set.</dcterms:abstract> <dc:creator>Angelini, Patrizio</dc:creator> </rdf:Description> </rdf:RDF>
Angelini_2-zrihd4nlcfc35.pdf | 13 |