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.
A result not really fitting in one of the three above classes by @cite_7 considers the restricted case of SEFE where each edge has to be a sequence of horizontal and vertical segments with at most one bend per edge. They show that two graphs with maximum degree 2 always admit such a SEFE on a grid of size @math by adapting their linear-time algorithm computing an SGE for these types of graphs (on a larger grid).
@cite_7
2949400914
We prove that the geometric thickness of graphs whose maximum degree is no more than four is two. All of our algorithms run in O(n) time, where n is the number of vertices in the graph. In our proofs, we present an embedding algorithm for graphs with maximum degree three that uses an n x n grid and a more complex algorithm for embedding a graph with maximum degree four. We also show a variation using orthogonal edges for maximum degree four graphs that also uses an n x n grid. The results have implications in graph theory, graph drawing, and VLSI design.