Morphing geometric graphs is a classical problem in graph theory and compu-tational geometry with seminal results established by Cairns in 1944 [Amer. Math. Monthly, 51] and by Thomassen in 1983 [J. of Comb. Theor., Series B, 34]. Over the years, this prob-lem has been widely studied in the context of planar graphs, with notable recent results focusing on the complexity of the vertex trajectories (e.g., by Alamdari et al. in 2017 [SIAM J. Computing, 46(2)]). Despite such a rich literature, very little is known about the existence of morphs for non-planar graphs. We make a step towards this problem by showing that a morph always exists for a meaningful family of 1-plane geometric graphs. While our proof is constructive, the vertices may follow trajectories of unbounded complexity.
On morphs of 1-plane graphs
Fabrizio Montecchiani;
2022
Abstract
Morphing geometric graphs is a classical problem in graph theory and compu-tational geometry with seminal results established by Cairns in 1944 [Amer. Math. Monthly, 51] and by Thomassen in 1983 [J. of Comb. Theor., Series B, 34]. Over the years, this prob-lem has been widely studied in the context of planar graphs, with notable recent results focusing on the complexity of the vertex trajectories (e.g., by Alamdari et al. in 2017 [SIAM J. Computing, 46(2)]). Despite such a rich literature, very little is known about the existence of morphs for non-planar graphs. We make a step towards this problem by showing that a morph always exists for a meaningful family of 1-plane geometric graphs. While our proof is constructive, the vertices may follow trajectories of unbounded complexity.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
