Publikation: Morphing Triangle Contact Representations of Triangulations
Dateien
Datum
Autor:innen
Herausgeber:innen
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
URI (zitierfähiger Link)
DOI (zitierfähiger Link)
Internationale Patentnummer
Link zur Lizenz
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
A morph is a continuous transformation between two representations of a graph. We consider the problem of morphing between contact representations of a plane graph. In an -contact representation of a plane graph G, 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 G. In a morph between two -contact representations we insist that at each time step (continuously throughout the morph) we have an -contact representation. We focus on the case when is the family of triangles in 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. Moreover, they naturally correspond to 3-orientations. Thus, they provide a natural case to study regarding morphs of contact representations of plane graphs. We characterize the pairs of RT-representations admitting a morph between each other via the respective 3-orientations. Our characterization leads to a polynomial-time algorithm to decide whether there is a morph between two RT-representations of an n-vertex plane triangulation, and, if so, computes a morph with steps. Each of these steps is a linear morph moving the endpoints of each triangle at constant speed along straight-line trajectories. Our characterization also implies 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.
Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
Schlagwörter
Konferenz
Rezension
Zitieren
ISO 690
ANGELINI, Patrizio, Steven CHAPLICK, Sabine CORNELSEN, Giordano DA LOZZO, Vincenzo ROSELLI, 2023. Morphing Triangle Contact Representations of Triangulations. In: Discrete & Computational Geometry. Springer. 2023, 70(3), pp. 991-1024. ISSN 0179-5376. eISSN 1432-0444. Available under: doi: 10.1007/s00454-022-00475-9BibTex
@article{Angelini2023-03-15Morph-66489, year={2023}, doi={10.1007/s00454-022-00475-9}, title={Morphing Triangle Contact Representations of Triangulations}, number={3}, volume={70}, issn={0179-5376}, journal={Discrete & Computational Geometry}, pages={991--1024}, author={Angelini, Patrizio and Chaplick, Steven and Cornelsen, Sabine and Da Lozzo, Giordano and Roselli, Vincenzo}, note={DFG - Project-ID 50974019 - TRR 161 (B06) (Cornelsen)} }
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/66489"> <dcterms:abstract>A morph is a continuous transformation between two representations of a graph. We consider the problem of morphing between contact representations of a plane graph. In an -contact representation of a plane graph G, 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 G. In a morph between two -contact representations we insist that at each time step (continuously throughout the morph) we have an -contact representation. We focus on the case when is the family of triangles in 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. Moreover, they naturally correspond to 3-orientations. Thus, they provide a natural case to study regarding morphs of contact representations of plane graphs. We characterize the pairs of RT-representations admitting a morph between each other via the respective 3-orientations. Our characterization leads to a polynomial-time algorithm to decide whether there is a morph between two RT-representations of an n-vertex plane triangulation, and, if so, computes a morph with steps. Each of these steps is a linear morph moving the endpoints of each triangle at constant speed along straight-line trajectories. Our characterization also implies 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.</dcterms:abstract> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/66489"/> <dc:contributor>Da Lozzo, Giordano</dc:contributor> <dc:language>eng</dc:language> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2023-03-29T13:21:57Z</dc:date> <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/66489/1/Angelini_2-1eq9je17og8b75.pdf"/> <dc:contributor>Angelini, Patrizio</dc:contributor> <dcterms:title>Morphing Triangle Contact Representations of Triangulations</dcterms:title> <foaf:homepage rdf:resource="http://localhost:8080/"/> <dc:creator>Roselli, Vincenzo</dc:creator> <dc:contributor>Roselli, Vincenzo</dc:contributor> <dc:contributor>Chaplick, Steven</dc:contributor> <dcterms:rights rdf:resource="http://creativecommons.org/licenses/by/4.0/"/> <dc:creator>Cornelsen, Sabine</dc:creator> <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/66489/1/Angelini_2-1eq9je17og8b75.pdf"/> <dc:contributor>Cornelsen, Sabine</dc:contributor> <dc:creator>Chaplick, Steven</dc:creator> <dc:creator>Da Lozzo, Giordano</dc:creator> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2023-03-29T13:21:57Z</dcterms:available> <dcterms:issued>2023-03-15</dcterms:issued> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dc:rights>Attribution 4.0 International</dc:rights> <dc:creator>Angelini, Patrizio</dc:creator> </rdf:Description> </rdf:RDF>