A Survey on Graph Drawing Beyond Planarity <s> Simultaneous RAC Embedding (SRE). Given two planar graphs <s> We consider the problem of simultaneous embedding of planar graphs. There are two variants of this problem, one in which the mapping between the vertices of the two graphs is given and another in which the mapping is not given. In particular, given a mapping, we show how to embed two paths on an n ×n grid, and two caterpillar graphs on a 3n ×3n grid. We show that it is not always possible to simultaneously embed three paths. If the mapping is not given, we show that any number of outerplanar graphs can be embedded simultaneously on an O(n) ×O(n) grid, and an outerplanar and general planar graph can be embedded simultaneously on an O(n 2) ×O(n 2) grid. <s> BIB001 </s> A Survey on Graph Drawing Beyond Planarity <s> Simultaneous RAC Embedding (SRE). Given two planar graphs <s> Two graphs $G_1=(V,E_1)$ and $G_2=(V,E_2)$ admit a geometric simultaneous embedding if there exists a set of points P and a bijection M: P ->V that induce planar straight-line embeddings both for $G_1$ and for $G_2$. While it is known that two caterpillars always admit a geometric simultaneous embedding and that two trees not always admit one, the question about a tree and a path is still open and is often regarded as the most prominent open problem in this area. We answer this question in the negative by providing a counterexample. Additionally, since the counterexample uses disjoint edge sets for the two graphs, we also negatively answer another open question, that is, whether it is possible to simultaneously embed two edge-disjoint trees. As a final result, we study the same problem when some constraints on the tree are imposed. Namely, we show that a tree of depth 2 and a path always admit a geometric simultaneous embedding. In fact, such a strong constraint is not so far from closing the gap with the instances not admitting any solution, as the tree used in our counterexample has depth 4. <s> BIB002 </s> A Survey on Graph Drawing Beyond Planarity <s> Simultaneous RAC Embedding (SRE). Given two planar graphs <s> Simultaneous embedding is concerned with simultaneously representing a series of graphs sharing some or all vertices. This forms the basis for the visualization of dynamic graphs and thus is an important field of research. Recently there has been a great deal of work investigating simultaneous embedding problems both from a theoretical and a practical point of view. We survey recent work on this topic. <s> BIB003 </s> A Survey on Graph Drawing Beyond Planarity <s> Simultaneous RAC Embedding (SRE). Given two planar graphs <s> In this paper, we study the geometric RAC simultaneous drawing problem: Given two planar graphs that share a common vertex set, a geometric RAC simultaneous drawing is a straight-line drawing in which each graph is drawn planar, there are no edge overlaps, and, crossings between edges of the two graphs occur at right angles. We rst prove that two planar graphs admitting a geometric simultaneous drawing may not admit a geometric RAC simultaneous drawing. We further show that a cycle and a matching always admit a geometric RAC simultaneous drawing.We also study a closely related problem according to which we are given a planar embedded graph G and the main goal is to determine a geometric drawing of G and its weak dual G such that: (i) G and G are drawn planar, (ii) each vertex of the dual is drawn inside its corresponding face of G and, (iii) the primal-dual edge crossings form right angles. We prove that it is always possible to construct such a drawing if the input graph is an outerplanar embedded graph. <s> BIB004 </s> A Survey on Graph Drawing Beyond Planarity <s> Simultaneous RAC Embedding (SRE). Given two planar graphs <s> Given two planar graphs that are defined on the same set of vertices, a RAC simultaneous drawing is one in which each graph is drawn planar, there are no edge overlaps and the crossings between the two graphs form right angles. The geometric version restricts the problem to straight-line drawings. It is known, however, that there exists a wheel and a matching which do not admit a geometric RAC simultaneous drawing. In order to enlarge the class of graphs that admit RAC simultaneous drawings, we allow bends in the resulting drawings. We prove that two planar graphs always admit a RAC simultaneous drawing with six bends per edge each, in quadratic area. For more restricted classes of planar graphs (i.e., matchings, paths, cycles, outerplanar graphs and subhamiltonian graphs), we manage to significantly reduce the required number of bends per edge, while keeping the area quadratic. <s> BIB005 </s> A Survey on Graph Drawing Beyond Planarity <s> Simultaneous RAC Embedding (SRE). Given two planar graphs <s> Let $$\langle G_r,G_b \rangle $$ be a pair of plane st-graphs with the same vertex set V. A simultaneous visibility representation with L-shapes of $$\langle G_r,G_b \rangle $$ is a pair of bar visibility representations $$\langle \varGamma _r,\varGamma _b\rangle $$ such that, for every vertex $$v \in V$$, $$\varGamma _rv$$ and $$\varGamma _bv$$ are a horizontal and a vertical segment, which share an end-point. In other words, every vertex is drawn as an L-shape, every edge of $$G_r$$ is a vertical visibility segment, and every edge of $$G_b$$ is a horizontal visibility segment. Also, no two L-shapes intersect each other. An L-shape has four possible rotations, and we assume that each vertex is given a rotation for its L-shape as part of the input. Our main results are: i a characterization of those pairs of plane st-graphs admitting such a representation, ii a cubic time algorithm to recognize them, and iii a linear time drawing algorithm if the test is positive. <s> BIB006
with the same vertex set, a simultaneous embedding (SE) of G 1 and G 2 is a pair of planar drawings, Γ 1 of G 1 and Γ 2 of G 2 , such that each vertex v ∈ V has the same position in Γ 1 and Γ 2 (the edges of Γ 1 can cross those of Γ 2 ). The SE problem was introduced a decade ago, motivated by several practical scenarios BIB001 , and since then it has been widely studied (see, e.g., BIB003 for a survey). A Simultaneous RAC Embedding (SRE) of two graphs G 1 and G 2 is an SE with the additional property that the union of the two planar drawings Γ 1 and Γ 2 is RAC. The SRE problem was originally introduced for straight-line drawings BIB004 , showing that only restricted pairs of planar subgraphs admit such an embedding; for example, a wheel and a cycle might not admit a straight-line SRE. In general, deciding whether a pair of graphs admits an SRE with straight-line edges is NP-hard  , while every pair of planar graphs has an SRE with at most six bends per edge BIB005 . The number of bends per edge can be further reduced for some combinations of specific subfamilies of planar graphs. Moreover, an SRE with at most two bends exists for those pairs of graphs admitting a special type of visibility representation in which vertices are axis-aligned L-shapes and edges are vertical or horizontal lines of sight connecting pairs of such shapes BIB006 . Another variant of SE in graph drawing beyond planarity considers a simultaneous embedding of two graphs G 1 and G 2 in which each of the two drawings Γ 1 and Γ 2 is allowed to have some desired type of crossings. This setting generalizes the classical SE instead of restricting it. For example, Di Giacomo et al. study Simultaneous Geometric Quasi Planar Embedding (SGQPE), where each Γ i is a straight-line quasi planar drawing  . They show, for instance, that a tree and a path always admit an SGQPE, in contrast to the negative result in the simultaneous geometric planar embedding setting BIB002 .