Planar and Quasi-Planar Simultaneous Geometric Embedding
Emilio Di Giacomo, Walter Didimo, Giuseppe Liotta, Henk Meijer, Stephen Wismath · The Computer Journal · 2015
A simultaneous geometric embedding (SGE) of two planar graphs |$G_1$| and |$G_2$| with the same vertex set is a pair of straight-line planar drawings |$\Gamma _1$| of |$G_1$| and |$\Gamma _2$| of |$G_2$| such that each vertex is drawn at the same point in |$\Gamma _1$| and |$\Gamma _2$|. Many papers have been devoted to the study of which pairs of graphs admit a SGE, and both positive and negative results have been proved. We extend the study of SGE, by introducing and characterizing a new class of planar graphs that makes it possible to immediately extend several positive results that rely on the property of strictly monotone paths. Moreover, we introduce a relaxation of the SGE setting where |$\Gamma _1$| and |$\Gamma _2$| are required to be quasi-planar (i.e. they can have crossings provided that there are no three mutually crossing edges). This relaxation allows for the simultaneous embedding of pairs of planar graphs that are not simultaneously embeddable in the classical SGE setting and opens up several new interesting research questions.