Drawing Simultaneously Embedded Graphs with Few Bends - Graph Drawing - page 40

The problem S GE is NP-hard [8] and, moreover, there are quite restricted graph
classes that do not always admit an S GE ,e.g., even a path and a tree do not always admit
an S GE [3]. To date no efficient testing algorithms for a non-trivial class of restricted
input instances is known.
In contrast, the complexity of testing the existence of a S EFE drawing for two input
graphs is a long-standing open problem. Jünger and Schulz [13] showed that the prob-
lem is actually equivalent to determining planar embeddings of the two input graphs
that induce the same embedding on the common graph. For three input graphs the prob-
lem is NP-complete [9]. In recent years considerable progress has been made, providing
efficient testing algorithms for increasingly general sets of input instances. Most of the
results revolve around assumptions on the connectivity or the maximumdegree of the in-
put graphs and the common subgraph. It is known that S EFE can be tested in polynomial
time if the common subgraph has a fixed planar embedding [1], if the common graph
is biconnected [2,10], if the two input graphs are biconnected and the common graph is
connected or a forest [6], and if each connected component of the common graph is either
biconnected or subcubic [18]. The last result can be improved to also allow connected
components of the common graph that are outerplanar and whose cutvertices have de-
gree at most 3 in the common graph [4]. See the recent survey by Bläsiusetal.[5]for
further details.
While the rephrasing of the original drawing problem S EFE as an embedding prob-
lem has certainly been fundamental in starting this evolution, it also comes at a
disadvantage. Typically, the outputs of the above-mentioned algorithms are just pla-
nar embeddingsoftheinput graphs, i.e., rotation systems and relative positions of the
connected components, that coincide on the common graph. We call this a S EFE em-
bedding . To obtain a visualization, it is necessary to transform this combinatorial de-
scription of a drawing into an actual drawing while preserving the given embedding.
For clarity, we refer to such a drawing as a S EFE drawing and say that the S EFE draw-
ing realizes the corresponding S EFE embedding. Although the complexity of S EFE is
still open, the existing results allow efficient testing algorithms for a largerangeofin-
stances, increasing the importance of the realization problem. The very first result on
simultaneousdrawings with few bends was obtained by Erten and Kobourov [7] in the
context of S IMULTANEOUS E MBEDDING , where one only requires that common ver-
tices are drawn the same, whereas shared edges may be drawn differently for different
input graphs. They showed that three bends per edgesuffice if the common graph does
not contain any edges. Haeupler et al. [10] initiated the study of the realization problem
for S EFE embeddings and showed that for any instance where the common graph is
connected, it is always possible to find a S EFE drawing realizing a given S EFE embed-
ding in such a way that one of the input graphs is drawn straight-line, whereas the other
graph has at most as many bends per edgeasthenumber of vertices in the common sub-
graph. We show that a constant number of bends per edgesuffices if bends are allowed
on the exclusive edges of both graphs, even if the common graph is disconnected.
A related notion is partially embedded graphs , where one seeks to extend a given
drawing of a subgraph (partial drawing) into a planar drawing of the whole graph.
Similar to the simultaneousdrawing problem, the partial embedding problem has been
studied both in the topological setting [1,12,18] and in the straight-line setting [15,17].