Type of Publication:  Contribution to a conference collection 
Publication status:  Accepted 
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 
To Appear in:  35th International Symposium on Computational Geometry (SoCG 2019) / Barequet, Gill; Wang, Yusu (ed.).  Wadern : Schloss Dagstuhl  LeibnizZentrum für Informatik, 2019.  (LIPIcs : Leibniz International Proceedings in Informatics ; 129).  eISSN 18688969 
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 lowerright half of axisparallel rectangles. Such RTrepresentations 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 straightline trajectories. We provide a polynomialtime algorithm that decides whether there is a piecewise linear morph between two RTrepresentations 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 4connected plane triangulations there is a morph between every pair of RTrepresentations where the ``topmost'' triangle in both representations corresponds to the same vertex. This shows that the realization space of such RTrepresentations of any 4connected plane triangulation forms a connected set.

Subject (DDC):  004 Computer Science 
Bibliography of Konstanz:  Yes 
Files  Size  Format  View 

There are no files associated with this item. 
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  LeibnizZentrum für Informatik. eISSN 18688969
@inproceedings{Angelini2019Morph45596, title={Morphing Contact Representations of Graphs}, year={2019}, number={129}, address={Wadern}, publisher={Schloss Dagstuhl  LeibnizZentrum 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/22rdfsyntaxns#" xmlns:bibo="http://purl.org/ontology/bibo/" xmlns:dspace="http://digitalrepositories.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.unikonstanz.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> <dc:contributor>Da Lozzo, Giordano</dc:contributor> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">20190405T12:30:58Z</dcterms:available> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">20190405T12:30:58Z</dc:date> <dcterms:isPartOf rdf:resource="https://kops.unikonstanz.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> <dcterms:issued>2019</dcterms:issued> <dspace:isPartOfCollection rdf:resource="https://kops.unikonstanz.de/rdf/resource/123456789/36"/> <bibo:uri rdf:resource="https://kops.unikonstanz.de/handle/123456789/45596"/> <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 lowerright half of axisparallel rectangles. Such RTrepresentations 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 straightline trajectories. We provide a polynomialtime algorithm that decides whether there is a piecewise linear morph between two RTrepresentations 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 4connected plane triangulations there is a morph between every pair of RTrepresentations where the ``topmost'' triangle in both representations corresponds to the same vertex. This shows that the realization space of such RTrepresentations of any 4connected plane triangulation forms a connected set.</dcterms:abstract> <dc:creator>Angelini, Patrizio</dc:creator> </rdf:Description> </rdf:RDF>