The topic of simultaneous embeddings of planar graphs is a common sight in the recent graph drawing literature. A recent survey of the topic is given by Bläsius, Kobourov and Ritter. I am interested in the case of Simultaneous Embeddings with Fixed Edges (SEFE), which is the following problem:

Input: Two graphs $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$, sharing a common subgraph $G=(V=V_1 \cap V_2, E=E_1 \cap E_2)$.

Problem: Do there exist planar embeddings of $G_1$ and $G_2$ such that the vertices and the edges of $G$ are mapped to the same vertices and Jordan arcs in both embeddings (i.e., do there exist two embeddings which agree on $G$).

The complexity of SEFE is an open problem.

According to the aforementioned survey, this problem can be solved in linear time when the intersection graph $G$ is a star, as it can be reduced to a variant of $2$-page embedding, for which an algorithm is known. However, looking at the corresponding paper, the input is slightly different: the vertex sets of $G_1$ and $G_2$ are assumed to be the same. Without this assumption, neither the reduction nor the corresponding algorithm seem to adapt (at least the definition of splitters should be modified).

Hence my questions:

  • Maybe I am missing something obvious: In general for the SEFE problem, is there an easy way to reduce the case of $V_1 \neq V_2$ to the equal vertex set case? (obviously one can just add copies of the exclusive vertices of $V_1$ to $V_2$ and vice versa, but this changes a lot the structure and the connectivity of the intersection graph, which is critical for most algorithms)
  • If not, is a polynomial-time algorithm known to solve the SEFE problem when the intersection graph is a star but the vertex sets are different?
  • $\begingroup$ Just a note: in Gassner et al., "Simultaneous Graph Embeddings with Fixed Edges" (in which they prove that the decision problem is NP-complete when there are three or more input graphs) the SEFE problem is defined on a set of graphs that share the same vertex set $V$. $\endgroup$ Commented Nov 5, 2014 at 15:41


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.