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.
An interesting additional restriction to SGE s was considered by @cite_34 , combining SGE with the RAC drawing convention (RAC -- Right-Angular Crossing). They try to find an SGE such that crossings between exclusive edges of different graphs are restricted to right-angular crossings. consider only the case where the edge sets of both graphs are disjoint. They present one negative and one positive result for this problem. The negative result consists of a wheel and a cycle not admitting an SGE with right-angular crossings. On the other hand they show the existence of such a drawing on a small integer grid for the case that one of the graphs is a path or a cycle and the other is a matching. Moreover, they give a linear-time algorithm to compute such a drawing.
@cite_34
2107611155
In this paper, we study the geometric RAC simultaneous drawing problem: Given two planar graphs that share a common vertex set but have disjoint edge sets, a geometric RAC simultaneous drawing is a straight-line drawing in which (i) each graph is drawn planar, (ii) there are no edge overlaps, and, (iii) crossings between edges of the two graphs occur at right-angles. We first 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, which can be constructed in linear time.