Simultaneous embedding: edge orderings, relative positions, cutvertices (Q1751092)

Given two planar graphs, a \textit{simultaneous embedding with fixed edges} consists of planar embeddings of each in which the vertices and edges that appear in both graphs coincide in the embeddings. No polynomial-time algorithm is currently known for determining whether two graphs admit such a simultaneous embedding, but the problem is not known to be NP-complete. This paper makes two main contributions. First, it develops linear-time pre-processing strategies for simplifying or reducing the graphs in such a way that a simultaneous embedding of the original graphs can be determined from one for the reduced graphs. Second, when a certain structural restriction on the graphs holds, an algorithm for simultaneous embedding that runs in cubic time is developed. The paper is quite technical, but is relatively self-contained. Obstacles to obtaining a general polynomial-time algorithm, and possible methods to overcome them, are discussed.