Computing a morph between two drawings of a graph is a classical problem in computational geometry and graph drawing. While this problem has been widely studied in the context of planar graphs, very little is known about the existence of topology-preserving morphs for pairs of non-planar graph drawings. We make a step towards this problem by showing that a topology-preserving morph always exists for drawings of a meaningful family of 1-planar graphs. While our proof is constructive, the vertices may follow trajectories of unbounded complexity.
On Morphing 1-Planar Drawings
Montecchiani F.;
2021
Abstract
Computing a morph between two drawings of a graph is a classical problem in computational geometry and graph drawing. While this problem has been widely studied in the context of planar graphs, very little is known about the existence of topology-preserving morphs for pairs of non-planar graph drawings. We make a step towards this problem by showing that a topology-preserving morph always exists for drawings of a meaningful family of 1-planar graphs. While our proof is constructive, the vertices may follow trajectories of unbounded complexity.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
