# Synchronized Planarity with Applications to Constrained Planarity
Problems††thanks: Work partially supported by DFG-grant Ru-1903/3-1.

Thomas Bläsius  Hasso Plattner Institute, University of Potsdam, Germany,
<EMAIL_ADDRESS>Simon D. Fink  Faculty of Informatics and Mathematics,
University of Passau, Germany<EMAIL_ADDRESS>Ignaz Rutter
Faculty of Informatics and Mathematics, University of Passau, Germany,
<EMAIL_ADDRESS>
###### Abstract

We introduce the problem Synchronized Planarity. Roughly speaking, its input
is a loop-free multi-graph together with synchronization constraints that,
e.g., match pairs of vertices of equal degree by providing a bijection between
their edges. Synchronized Planarity then asks whether the graph admits a
crossing-free embedding into the plane such that the orders of edges around
synchronized vertices are consistent. We show, on the one hand, that
Synchronized Planarity can be solved in quadratic time, and, on the other
hand, that it serves as a powerful modeling language that lets us easily
formulate several constrained planarity problems as instances of Synchronized
Planarity. In particular, this lets us solve Clustered Planarity in quadratic
time, where the most efficient previously known algorithm has an upper bound
of $O\left(n^{16}\right)$.

##  1 Introduction

A graph is _planar_ if it admits an embedding into the plane that has no edge
crossings. Planarity is a well-studied concept that facilitates beautiful
mathematical structures [23, 10], allows for more efficient algorithms [22],
and serves as a cornerstone in the context of network visualization [30]. With
that said, it is not surprising that various generalizations, extensions, and
constrained variants of the Planarity problem have been studied [28]. Examples
are Clustered Planarity, where the planar embedding additionally has to
respect a laminar family of clusters [26, 9]; Constrained Planarity, where the
orders of edges incident to vertices are restricted, e.g., by PQ-trees [7];
Book Embeddings, where the vertices have to be placed on a straight line (the
spine of the book) while edges are embedded into distinct half-planes (the
pages of the book) [5]; and Simultaneous Planarity, where two or more graphs
that share a common subgraph should be embedded such that the embeddings
coincide on the shared part [6].

For planar embeddings, there is the important notion of _rotation_. The
rotation of a vertex is the order of incident edges around it. Many of the
above planarity variants come down to the question whether there are
embeddings of one or multiple graphs such that the rotations of certain
vertices are in sync in a certain way. Inspired by this observation, by the
Atomic Embeddability problem [18], and by the cluster decomposition tree (CD-
tree) [9], we introduce a new planarity variant. _Synchronized Planarity_ has
a loop-free multi-graph together with two types of synchronization constraints
as input. Each _Q-constraint_ is given as a subset of vertices together with a
fixed reference rotation for each of these vertices. The Q-constraint is
satisfied if and only if either all these vertices have their reference
rotation or all these vertices have the reversed reference rotation. Vertices
appearing in Q-constraints are called _Q-vertices_ and all remaining vertices
are _P-vertices_.111The names are based on PQ-trees, where Q- and P-nodes have
fixed and arbitrary rotation, respectively. A _P-constraint_ between two
P-vertices $u$ and $v$ defines a bijection between the edges incident to $u$
and $v$. It is satisfied if and only if $u$ and $v$ have the opposite rotation
under this bijection. We require that the P-constraints form a matching, i.e.,
no vertex appears in more than one P-constraint. The decision problem
Synchronized Planarity now asks whether the given graph can be embedded such
that all Q- and all P-constraints are satisfied.

Synchronized Planarity serves as a powerful modeling language that lets us
express various other planarity variants using simple linear-time reductions.
Specifically, we provide such reductions for Clustered Planarity, Atomic
Embeddability, Partially PQ-constrained Planarity, and Simultaneous Embedding
with Fixed Edges with a connected shared graph (Connected SEFE). Our main
contribution is an algorithm that solves Synchronized Planarity, and thereby
all the above problems, in quadratic time.

###  1.1 Technical Contribution

Our result impacts different planarity variants that have been studied
previously. Before discussing them individually in the context of previous
publications, we point out a common difficulty that has been a major barrier
for all of them, and briefly sketch how we resolve it.

Consider the following constraint on the rotation of a single vertex. Assume
its incident edges are grouped and we only allow orders where no two groups
alternate, i.e., if $e_{1}$ and $e_{2}$ are in one group and $e_{3}$ and
$e_{4}$ are in a different group, then the subsequence
$e_{1},e_{3},e_{2},e_{4}$, its inverse, and all cyclic shifts are forbidden.
Such restrictions have been called _partition constraints_ before [9], and
they naturally emerge at cut-vertices where each 2-connected component joined
by the cut-vertex forms a group. A single partition constraint is not an issue
by itself. It is, however, difficult to deal with when combined with further
restrictions. This is why cut-vertices and disconnected clusters are a major
obstacle for SEFE [6] and Clustered Planarity [9], respectively.

The same issues appear for Synchronized Planarity, when we have a cut-vertex
$v$ that is involved in P-constraints, i.e., its rotation has to be
synchronized with the rotation of a different vertex $u$. We deal with these
situations as follows, depending on whether $u$ is also a cut-vertex or not.
If not, it is rather well understood which embedding choices impact the
rotation of $u$ and we can propagate this from $u$ to $v$.222We can also do
this if $v$ is not a cut-vertex. This breaks the synchronization of $u$ and
$v$ down into the synchronization of smaller embedding choices. This kind of
approach is a well-known technique that has been used before [7, 20]. In case
$u$ is also a cut-vertex, we are forced to actually deal with the embedding
choices emerging at cut-vertices. This is done by encapsulating the
restrictions on the rotations of $u$ and $v$ that are caused by the fact that
they are cut-vertices. All additional restrictions coming from embedding
choices in the 2-connected components are pushed away by introducing
additional P-constraints. After this, the cut-vertices $u$ and $v$ have very
simple structure, which can be resolved by essentially joining them together.
This procedure is formally described in Section 3.2 and illustrated in Figures
2 and 3.

We note that the recent break through result by Fulek and Tóth [18] also
resolves the cut-vertex issue, as they in particular solve Clustered Planarity
in polynomial time. However, besides being much slower333The algorithm for
Atomic Embeddability runs in $O(n^{8})$ time. The solution for Clustered
Planarity is done via a reduction with a quadratic blow up, leading to a
running time of $O(n^{16})$. their algorithm is significantly more
complicated, which makes it impossible to pinpoint the new insight that helps
to deal with cut-vertices.

###  1.2 Related Work

Clustered Planarity was first considered by Lengauer [26] and later
rediscovered by Feng et al. [16]. In both cases, the authors give polynomial-
time algorithms for the case that each cluster induces a connected graph. The
complexity of the general problem that allows disconnected clusters has been
open for 30 years. In that time, many special cases have been shown to be
polynomial-time solvable [3, 12, 17, 19] before Fulek and Tóth [18] recently
settled Clustered Planarity in P. The core ingredient for this is their
$O(n^{8})$ algorithm for the Atomic Embeddability problem. It has two graphs
$G$ and $H$ as input. Roughly speaking, $H$ describes a 3-dimensional molecule
structure with atoms represented by spheres and connections (a.k.a. pipes)
represented by cylinders. The other graph $G$ comes with a map to the molecule
structure that maps each vertex to an atom such that two neighboring vertices
lie on the same atom or on two atoms connected by a pipe. Atomic Embeddability
then asks whether $G$ can be embedded onto the molecule structure such that no
edges cross; see Section 4 for a formal definition.

Atomic Embeddability has been introduced as a generalization of the
Thickenability problem that appears in computational topology [1]. It asks for
a given 2-dimensional polyhedron whether there is a 3-dimensional manifold it
can be embedded into. It reduces to Atomic Embeddability by representing the
polyhedron’s vertices and edges using the molecule structure and its faces by
mapping disjoint cycles onto it [18]. Thus, the above $O(n^{8})$ algorithm for
Atomic Embeddability also solves Thickenability. Carmesin [11] previously
showed that Thickenability can be solved in quadratic time if the given
polyhedron is simply connected. Moreover, embedding general polyhedra into
$\mathbb{R}^{3}$ (instead of into any 3-dimensional manifold) is NP-hard [14].

To solve Clustered Planarity, Fulek and Tóth [18] use the reduction of Cortese
and Patrignani [13] to Independent Flat Clustered Planarity, which they then
reduce further to Thickenability. As the first reduction has a quadratic blow-
up, this yields an $O(n^{16})$ algorithm for Clustered Planarity. The last
reduction to Thickenability is based on a combinatorial characterization of
Thickenability by Neuwirth [27], which basically states that multiple graphs
have to be embedded consistently, i.e., such that the rotation is synchronized
between certain vertex pairs of different graphs. This makes Thickenability a
special case of Synchronized Planarity. Via the reduction from Connected SEFE
to Clustered Planarity given by Angelini and Da Lozzo [2], the above result
extends to Connected SEFE, which was a major open problem in the context of
simultaneous graph representations [8]. We flatten this chain of reductions by
giving a simple linear reduction from each of the problems Connected SEFE,
Clustered Planarity, and Atomic Embeddability to Synchronized Planarity,
yielding quadratic time algorithms for all of them. Moreover, the problem
Partially PQ-constrained Planarity, for which we also give a linear reduction
to Synchronized Planarity, has been solved in polynomial time before for
biconnected graphs [7] and in the non-partial setting where either all or none
of the edges of a vertex are constrained [20].

##  2 Preliminaries

A _partition_ of a base set $X$ is a grouping of its elements into non-empty
subsets, the _cells_ , so that every element is contained in exactly one cell.
We assume a set implementation allowing constant-time insertion and removal of
elements, such as doubly-linked lists with pointers stored with the elements.
When referring to graphs, we generally mean _loop-free multi-graphs_. We
assume a graph representation that allows efficient manipulation, such as an
adjacency list with doubly-linked lists.

A _$k$ -wheel_ is a $k$-cycle, where each node is also connected to an
additional central node. A _star_ consists of a _center vertex_ and multiple
_ray vertices_ , where all edges have the center as one endpoint and a ray as
the other endpoint. A _multi-star_ is a star where each ray may have multiple
edges connecting it to the center.

##### Drawings, Embeddings and Cyclic Orders.

A _(topological) drawing_ $\Gamma$ of a graph is a mapping of every vertex $v$
to a point $p_{v}\in\mathbb{R}^{2}$ in the plane and a mapping of every edge
$\\{u,v\\}$ to a Jordan arc having $p_{u}$ and $p_{v}$ as endpoints. A drawing
uniquely defines cyclic orders of edges incident to the same vertex. Drawings
with the same cyclic orders are considered equivalent, their equivalence class
is called _(combinatorial) embedding_. For an embedding $\mathcal{E}$, we use
$\mathcal{E}(u)$ to denote the cyclic order of the edges incident to $u$ as
given by $\mathcal{E}$, which is also called the _rotation_ of $u$. For a
(cyclic) order $\sigma=\langle x_{1},\ldots,x_{k}\rangle$ of $k$ elements, we
use $\overline{\sigma}=\langle x_{k},\ldots,x_{1}\rangle$ to denote its
reversal.

##### Synchronized Planarity.

Synchronized Planarity instances are tuples
$I=(G,\mathcal{P},\mathcal{Q},\psi)$, where

  1. 1.

$G=(P\cup Q,E)$ is a (loop-free) multi-graph with a set $P$ of P-vertices and
a set $Q$ of Q-vertices,

  2. 2.

$\mathcal{Q}$ is a partition of $Q$,

  3. 3.

$\mathcal{\psi}$ is a mapping that assigns a rotation to each Q-vertex, and

  4. 4.

$\mathcal{P}$ is a collection of triples $(u,v,\varphi_{uv})$, where $u$ and
$v$ are P-vertices, $\varphi_{uv}$ is a bijection between their incident
edges, and each P-vertex occurs in at most one triple of $\mathcal{P}$.

We call the triples $\rho=(u,v,\varphi_{uv})$ in $\mathcal{P}$ _pipes_. Pipes
are not directed and we identify $(u,v,\varphi_{uv})$ and $(v,u,\varphi_{vu})$
with $\varphi_{vu}=\varphi_{uv}^{-1}$. We also define
$\operatorname{deg}(\rho)=\operatorname{deg}(u)=\operatorname{deg}(v)$. If two
P-vertices are connected by a pipe, we call them _matched_ , whereas all other
P-vertices and all Q-vertices are called _unmatched_.

The planar embedding $\mathcal{E}$ of $G$ _satisfies the cell_
$X\in\mathcal{Q}$ if it is either $\mathcal{E}(v)=\psi(v)$ for all $v\in X$ or
$\mathcal{E}(v)=\overline{\psi(v)}$ for all $v\in X$. We say that the
embedding satisfies the _Q-constraints_ if it satisfies all cells, that is
vertices in the same cell of the partition $\mathcal{Q}$ are consistently
oriented. The embedding $\mathcal{E}$ _satisfies the pipe_
$\rho=(u,v,\varphi_{uv})$ if it is
$\varphi_{uv}(\mathcal{E}(u))=\overline{\mathcal{E}(v)}$, i.e., they have
opposite rotations under the bijection $\varphi_{uv}$. We say that the
embedding satisfies the _P-constraints_ if it satisfies all pipes. The
embedding $\mathcal{E}$ is called _valid_ if it satisfies the P-constraints
and the Q-constraints. The problem Synchronized Planarity asks whether a given
instance $I=(G,\mathcal{P},\mathcal{Q},\psi)$ admits a valid embedding.

##### PQ-Trees and Embedding Trees.

A _PQ-tree_ represents a set of circular orders of its leaves by partitioning
its inner nodes into two classes: For _Q-nodes_ the rotation of incident edges
is fixed up to reversal, for _P-nodes_ , this order can be chosen arbitrarily.
Rooted PQ-trees have initially been studied by Booth and Lueker [10]. There is
an equivalence between rooted and unrooted PQ-trees [24], where the latter are
also called PC-trees [29]. We thus do not distinguish between both and simply
use the term PQ-trees. We call a PQ-tree _trivial_ if it has a single inner
node that is a P-node.

For a vertex of a planar graph, all rotations induced by planar embeddings can
efficiently be represented by a PQ-tree [10]. This PQ-tree is also called the
_embedding tree_ of the respective node and can be computed in time linear in
the size of the graph [7]. When we speak about the embedding tree of a vertex
in an instance of Synchronized Planarity, we assume that this PQ-tree does not
allow rotations directly resulting in a Q-vertex having any other rotation
than its default ordering or the reverse thereof. This can easily be assured
as follows. Note that for a Q-vertex $v\in G$, $\psi(v)$ is the default cyclic
ordering of the $k$ edges incident to $v$. We can subdivide each edge incident
to $v$ and connect each pair of two of the new nodes if the edges they
subdivide are consecutive in the cyclic order $\psi(v)$. Note that this
generates a $k$-wheel with center $v$ and that there are exactly two planar
rotations of the center of a wheel, which are the reverse of each other. This
thus ensures that in any planar embedding, the Q-vertex $v$ automatically has
either its default order or its reverse [20]. We always generate the embedding
trees based on the graph where each Q-vertex in $G$ was replaced with its
respective wheel.

##### Connected Components.

A separating $k$-set is a set of $k$ vertices whose removal increases the
number of connected components. Separating 1-sets are called _cut-vertices_ ,
while separating 2-sets are called _separation pairs_. A connected graph is
_biconnected_ if it does not have a cut-vertex. A biconnected graph is
_triconnected_ if it does not have a separation pair. Maximal biconnected
subgraphs are called _blocks_. A vertex that is not a cut-vertex and thus
resides within an unique block is called _block-vertex_.

Hopcroft and Tarjan [23] define a graph decomposition into triconnected
components, also called _SPQR-tree_ [4], where the components come in three
shapes: _bonds_ consist of two vertices called _poles_ connected by multiple
parallel edges, _polygons_ consist of a simple cycle, and _rigids_ , whose
embeddings are unique up to reflection. Each edge of these components is
either a _real edge_ representing a single edge of the original graph, or a
_virtual edge_ representing a subgraph.

Every planar embedding of a biconnected planar graph can be obtained from an
arbitrary planar embedding by flipping its rigids and reordering the parallel
edges in its bonds [23]. The decomposition can be computed in linear time and
can be used to efficiently represent all combinatorial embeddings [21].

##### Splits and Joins of Graphs and Embeddings.

Let $G=(V,E)$ be a graph. We call a partition $C=(X,Y)$ of $V$ into two
disjoint cells a _cut_ of $G$. The edges $E(C)$ that have their endpoints in
different cells, i.e., that cross the cut, are called _cut edges_. The _split_
of $G$ at $C=(X,Y)$ is the disjoint union of the two graphs obtained by
contracting $X$ and $Y$ to a single vertex $x$ and $y$, respectively (keeping
possible multi-edges); see Figure 1. Note that the edges incident to $x$ and
$y$ are exactly the cut edges, yielding a natural bijection $\varphi_{xy}$
between them. Conversely, given two graphs
$G_{1}=(V_{1},E_{1}),G_{2}=(V_{2},E_{2})$ and vertices $x\in V_{1}$, $y\in
V_{2}$ together with a bijection $\varphi_{xy}$ between their incident edges,
we define their _join_ along $\varphi_{xy}$ as the graph $G=(V,E)$, where
$V=V_{1}\cup V_{2}\setminus\\{x,y\\}$ and $E$ contains all edges of $E_{1}\cup
E_{2}$ that are neither incident to $x$ nor to $y$, and for each edge $e=ux$
incident to $x$, $E$ contains an edge $uv$, where $v$ is the endpoint of
$\varphi_{xy}(e)$ distinct from $y$; see Figure 1. Observe that split and join
are inverse operations.

We say that a planar embedding $\mathcal{E}$ of a graph $G$ _respects_ a cut
$C=(X,Y)$ if and only if for a topological planar drawing $\Gamma$ of $G$ with
embedding $\mathcal{E}$ there exists a closed curve $\gamma$ such that (i)
$\gamma$ separates $X$ from $Y$, (ii) $\gamma$ crosses each edge in $E(C)$ in
exactly one point, and (iii) $\gamma$ does not cross any edge in $E\setminus
E(C)$; see Figure 1. We say that $\gamma$ _represents $C$ in $\Gamma$_.

If $\mathcal{E}$ respects $C$, a split at $C$ preserves $\mathcal{E}$ in the
following way. Let $G_{1}$ and $G_{2}$ be the graphs resulting from splitting
$G$ at $C$ and let $x\in V_{1}$ and $y\in V_{2}$ such that $\varphi_{xy}$
identifies their incident edges. Let $\Gamma$ be a topological planar drawing
with embedding $\mathcal{E}$ and let $\gamma$ be a curve in $\Gamma$ that
represents $C$ in $\Gamma$. We obtain planar drawings $\Gamma_{1}$ and
$\Gamma_{2}$ of $G_{1}$ and $G_{2}$ by contracting to a single point the side
of $\gamma$ that contains $V_{2}$ and $V_{1}$, respectively. We denote by
$\mathcal{E}_{1}$ and $\mathcal{E}_{2}$ the corresponding combinatorial
embeddings of $G_{1}$ and $G_{2}$. Note that by construction for each vertex
of $V_{1}\setminus\\{x\\}$ the rotations in $\mathcal{E}$ and
$\mathcal{E}_{1}$ coincide, and the same holds for vertices of
$V_{2}\setminus\\{y\\}$ in $\mathcal{E}$ and $\mathcal{E}_{2}$. Moreover, the
rotations $\mathcal{E}_{1}(x)$ and $\mathcal{E}_{2}(y)$ are determined by the
order in which the edges of $E(C)$ cross $\gamma$, and therefore they are
oppositely oriented, i.e.,
$\varphi_{xy}(\mathcal{E}_{1}(x))=\overline{\mathcal{E}_{2}(y)}$. We call
embeddings $\mathcal{E}_{1}$ and $\mathcal{E}_{2}$ with this property
_compatible with $\varphi_{xy}$_.

Conversely, we can join arbitrary embeddings $\mathcal{E}_{1}$ of $G_{1}$ and
$\mathcal{E}_{2}$ of $G_{2}$ that are compatible with $\varphi_{xy}$ by
assuming that $x$ and $y$ lie on the outer face, removing $x$ and $y$ from the
embeddings, and connecting the resulting half-edges according to
$\varphi_{xy}$. The result is a planar embedding $\mathcal{E}$ where for each
vertex $v\in V_{i}\setminus\\{x,y\\}$ it is
$\mathcal{E}(v)=\mathcal{E}_{i}(v)$ for $i=1,2$.

Figure 1: Joining and splitting two graphs at $x\in V_{1}$ and $y\in V_{2}$.
The bijection $\varphi_{xy}$ between their incident edges is shown as follows:
the two bold edges at the bottom are mapped to each other. The other edges are
mapped according to their order following the arrow upwards (i.e. clockwise
for $x$ and counter-clockwise for $y$).

######  Lemma 1.

Let $G=(V,E)$ be a planar graph and let $(X,Y)$ be a cut of $G$ such that $X$
and $Y$ induce connected subgraphs of $G$. Then every planar embedding of $G$
respects $(X,Y)$.

###### Proof.

Let $\mathcal{E}$ be a planar embedding of $G$. Since $X$ and $Y$ induce
connected subgraphs, it follows that no proper subset of $E(X,Y)$ is a cut.
Therefore, $(X,Y)$ is a so-called bond, which corresponds to a simple cycle
$C^{\star}$ in the dual graph $G^{\star}$ with respect to $\mathcal{E}$ [15,
Proposition 4.6.1], which in turn implies that $\mathcal{E}$ respects $(X,Y)$.
∎

######  Lemma 2.

Every planar embedding of a bipartite planar graph $G=(A\cup B,E)$ respects
the cut $(A,B)$.

###### Proof.

Let $\mathcal{E}$ be a planar embedding of $G$. We claim that we can augment
$G$ and its embedding $\mathcal{E}$ by additional edges in
$\binom{A}{2}\cup\binom{B}{2}$ to a graph $G^{\prime}$ with planar embedding
$\mathcal{E}^{\prime}$ such that $A$ and $B$ induce connected subgraphs. The
fact that $\mathcal{E}$ respects the cut $(A,B)$ then follows from Lemma 1.

We prove the existence of such an augmentation by induction on $|A|+|B|$. The
statement clearly holds if $|A|=|B|=1$. Therefore assume $|A|+|B|>2$ and
without loss of generality assume $|A|>2$. Then there is a face that contains
at least two vertices $a_{1},a_{2}$ of $A$. Let $G^{\prime}=(A^{\prime}\cup
B^{\prime},E^{\prime})$ be the bipartite planar graph with planar embedding
$\mathcal{E}^{\prime}$ resulting from adding the edges $a_{1}a_{2}$ and
contracting it into a single vertex $a$. By the inductive hypothesis, graph
$G^{\prime}$ with embedding $\mathcal{E}^{\prime}$ can be augmented to
bipartite $G^{\prime\prime}$ with embedding $\mathcal{E}^{\prime\prime}$ so
that $A^{\prime}$ and $B^{\prime}$ induce connected subgraphs. We now expand
$a$ into two separate vertices $a_{1},a_{2}$, undoing the previous
contraction. The resulting graph $G^{\prime\prime\prime}$ (including the edge
$a_{1}a_{2}$) with embedding $\mathcal{E}^{\prime\prime\prime}$ is the desired
augmentation. ∎

##  3 The Synchronized Planarity Problem

We give an algorithm for solving Synchronized Planarity for graphs with $n$
vertices and $m$ edges in $O(m^{2})$ time. Without loss of generality, we
assume that $G$ has no isolated vertices and thus $m\in\Omega(n)$.

###  3.1 High-Level Algorithm

Our approach hinges on three main ingredients, which we outline in the
following. The first are the three operations EncapsulateAndJoin, PropagatePQ,
and SimplifyMatching, each of which can be applied to pipes that satisfy
certain conditions. If an operation is applicable, it produces an equivalent
instance $I^{\prime}$ of Synchronized Planarity in linear time. Secondly we
show that if none of the operations is applicable, then $I$ has no pipes, and
we give a simple linear-time algorithm for computing a valid embedding in this
case. The third ingredient is a non-negative potential function $\phi$ for
instances of Synchronized Planarity. We show that it is upper-bounded by $2m$,
and that each of the three operations decreases it by at least 1.

Our algorithm is therefore extremely simple; namely, while the instance still
has a pipe, apply one of the operations to decrease the potential. Since the
potential function is initially bounded by $2m$, at most $2m$ operations are
applied, each taking $O(m)$ time. The resulting instance without pipes has
size $O(m^{2})$ and can be solved in linear time, thus the total running time
is $O(m^{2})$.

####  3.1.1 Conversion of small-degree P-vertices

The main difficulty in Synchronized Planarity stems from matched P-vertices.
However, P-vertices of degree up to 3 behave like Q-vertices in the sense that
their rotations are unique up to reversal. Throughout this paper, we
implicitly assume that P-vertices of degree less than 4 are converted into
Q-vertices using the auxillary operation ConvertSmall described in the
following. We therefore assume without loss of generality that P-vertices, and
in particular pipes, have degree at least 4.

Vertices of degree 3 have only two distinct rotations, which are the reverse
of each other. Vertices of degree less than 3 have a unique rotation, which
coincides with its reverse. We thus define operation ConvertSmall $(u,I)$ to
convert a P-vertex $u$ with $\deg(u)<4$ into a Q-vertex, resulting in an
instance
$I^{\prime}=(G^{\prime},\mathcal{P}^{\prime},\mathcal{Q}^{\prime},\psi^{\prime})$
where $G^{\prime}=(P^{\prime}\cup Q^{\prime},E)$. If $u$ is unmatched, we set
$P^{\prime}=P\setminus\\{u\\}$, $\mathcal{P}^{\prime}=\mathcal{P}$, and
$Q^{\prime}=Q\cup\\{u\\}$ and give $u$ it its own cell in
$\mathcal{Q}^{\prime}=\mathcal{Q}\cup\left\\{\\{u\\}\right\\}$. We fix an
arbitrary order $\psi^{\prime}(u)$ and let $\psi^{\prime}$ coincide with
$\psi$ for all other vertices. If the P-vertex $u$ is matched with another
P-vertex $v$, we can convert both of them to Q-vertices setting
$P^{\prime}=P\setminus\\{u,v\\},$ $Q^{\prime}=Q\cup\\{u,v\\}$, and
$\mathcal{P}^{\prime}=\mathcal{P}\setminus\\{(u,v,\varphi_{uv})\\}$. We also
put both together in a cell in
$\mathcal{Q}^{\prime}=\mathcal{Q}\cup\left\\{\\{u,v\\}\right\\}$, again
setting $\psi^{\prime}(u)$ as before, but now also defining
$\psi^{\prime}(v)=\overline{\varphi_{uv}(\psi^{\prime}(u))}$. Note that this
enforces that matched vertices $u$ and $v$ have opposite rotations under the
bijection $\varphi_{uv}$. All other P-vertices and their pipes remain
unaffected. Previous Q-vertices already in $Q$ are also unaffected.

######  Lemma 3.

Applying ConvertSmall to a P-vertex $u$ with $\deg(u)<4$ yields an equivalent
instance in constant time.

###### Proof.

First we show that the conversion preserves a valid embedding $\mathcal{E}$ of
$I$. It is $\mathcal{E}(u)=\psi^{\prime}(u)$ or
$\mathcal{E}(u)=\overline{\psi^{\prime}(u)}$. If $u$ is unmatched, it is the
only Q-vertex in its cell and thus $\mathcal{E}$ also satisfies the
Q-constraints of $I^{\prime}$. Otherwise, $u$ is matched with P-vertex $v$ and
as $\mathcal{E}$ satisfies the pipe $uv$ it is
$\varphi_{uv}(\mathcal{E}(u))=\overline{\mathcal{E}(v)}$. If
$\mathcal{E}(u)=\psi^{\prime}(u)$, we get
$\psi^{\prime}(v)=\overline{\varphi_{uv}(\psi^{\prime}(u))}=\overline{\varphi_{uv}(\mathcal{E}(u))}=\mathcal{E}(v)$,
satisfying the new Q-constraint. The case of
$\mathcal{E}(u)=\overline{\psi^{\prime}(u)}$ follows analogously. As the
underlying graph and all other pipes remain unchanged, $\mathcal{E}$ is valid
embedding of $I^{\prime}$.

Conversely, assume that $\mathcal{E}^{\prime}$ is a valid embedding for
$I^{\prime}$. If $u$ is the sole vertex in its cell, converting $u$ to a
P-vertex will not affect the validity of the embedding (and also not allow new
embeddings as $\deg(u)<4$). If $u$ shares its cell with vertex $v$, it is
$\mathcal{E}^{\prime}(u)=\psi^{\prime}(u)$ and
$\mathcal{E}^{\prime}(v)=\psi^{\prime}(v)$ or
$\mathcal{E}^{\prime}(u)=\overline{\psi^{\prime}(u)}$ and
$\mathcal{E}^{\prime}(v)=\overline{\psi^{\prime}(v)}$. As we chose
$\psi^{\prime}(v)=\overline{\varphi_{uv}(\psi^{\prime}(u))}$, inserting shows
that both cases satisfy the constraint
$\varphi_{uv}(\mathcal{E}(u))=\overline{\mathcal{E}(v)}$ of pipe $uv$. As the
underlying graph, all other pipes and Q-constraints remain unchanged,
$\mathcal{E}^{\prime}$ is valid embedding of $I$.

This concludes the proof of correctness of ConvertSmall. As all affected
vertices have degree at most 3, the time required to execute the operation is
constant. ∎

###  3.2 The EncapsulateAndJoin Operation

The purpose of the EncapsulateAndJoin operation is to communicate embedding
restrictions between two matched cut-vertices. Our approach here has two
steps: First we encapsulate the cut-vertices into their own independent multi-
star components, also disconnecting their incident blocks from each other. In
the second step, we join the multi-stars. Figures 2 and 3 show an example.

(a)

(b)

Figure 2: A matched cut-vertex (a) and the result of encapsulating it (b).

(a)

(b)

(c)

Figure 3: Two (encapsulated) matched cut-vertices (a). Depending on the
mapping $\varphi$, any bipartite graph can result from joining them. For
example, the graph (b) can result, which is equal to the square grid graph
shown in (c).

For an instance $I=(G,\mathcal{P},\mathcal{Q},\psi)$ of Synchronized
Planarity, let $\rho=(u,v,\varphi_{uv})$ be a pipe matching two cut-vertices
$u,v$ of connected components $C_{u},C_{v}$. Operation EncapsulateAndJoin
$(\rho,I)$ can be applied resulting in an instance
$I^{\prime}=(G^{\prime},\mathcal{P}^{\prime},\mathcal{Q}^{\prime},\psi^{\prime})$
using the following two steps. We first preprocess both cut-vertices to
_encapsulate_ them into their own separate multi-star components. Let
$C_{1},\dots,C_{k}$ be the connected components of $C_{u}-u$. We split $C_{u}$
along the cuts $(V(C_{i}),V\setminus V(C_{i}))$ for $i=1,\dots,k$. We denote
the vertices resulting from the split along $(V(C_{i}),V\setminus V(C_{i}))$
as $u_{i}$ and $u_{i}^{\prime}$, where $u_{i}$ results from contracting
$V\setminus V(C_{i})$ and $u_{i}^{\prime}$ results from contracting
$V(C_{i})$. Note that, after all splits, $u$ is the center of a multi-star
$C_{u}^{\prime}$ whose rays are the $u_{i}^{\prime}$. We add the pipes
$(u_{i},u_{i}^{\prime},\varphi_{u_{i}u_{i}^{\prime}})$ for $i=1,\dots,k$; see
Figure 2. The same procedure is also applied to $v$, resulting in an
intermediate instance $I^{\ast}$. In the second step, we _join_ the connected
components $C_{u}^{\prime}$ and $C_{v}^{\prime}$ at $u$ and $v$ along the
mapping $\varphi_{uv}$ of $\rho$ into a component $C_{uv}$. We also remove the
pipe $\rho$ from the $I^{\ast}$; all other parts of the instance remain
unchanged. Figure 3 shows a possible result of joining two multi-stars.

######  Lemma 4.

Applying EncapsulateAndJoin to a pipe $\rho$ yields an equivalent instance in
$O(\operatorname{deg}(\rho))$ time.

###### Proof.

By 1 a valid embedding $\mathcal{E}$ of an instance $I$ respects each of the
cuts $(V(C_{i}),V\setminus V(C_{i}))$ for $i=1,\dots,k$, yielding a planar
embedding $\mathcal{E}^{\ast}$ of $I^{\ast}$. By construction, it is
$\mathcal{E}^{\ast}(u_{i})=\overline{\mathcal{E}^{\ast}(u_{i}^{\prime})}$ for
$i=1,\dots,k$, i.e., each new pipe
$(u_{i},u_{i}^{\prime},\varphi_{u_{i}u_{i}^{\prime}})$ is satisfied and
$\mathcal{E}^{\ast}$ is a valid embedding of $I^{\ast}$. Conversely, if
$\mathcal{E}^{\ast}$ is a valid embedding of $I^{\ast}$, we can join $u_{i}$
with $u_{i}^{\prime}$ for $i=1,\dots,k$ to obtain a valid planar embedding
$\mathcal{E}$ of $I$, as the pipe
$(u_{i},u_{i}^{\prime},\varphi_{u_{i}u_{i}^{\prime}})$ ensures that
$\mathcal{E}^{\ast}$ is compatible with $\varphi_{u_{i}u_{i}^{\prime}}$. The
same applies to $C_{v}$.

If $\mathcal{E}^{\ast}$ is a valid embedding for $I^{\ast}$, it satisfies the
pipe $(u,v,\varphi_{uv})$ and we can join the embedding at $u$ and $v$ via
$\varphi_{uv}$ to obtain a planar embedding $\mathcal{E}^{\prime}$ of
$G^{\prime}$. Since the rotations of vertices different from $u,v$ are
unaffected, $\mathcal{E}^{\prime}$ is valid for $I^{\prime}$. Conversely,
assume that $\mathcal{E}^{\prime}$ is a valid embedding for $I^{\prime}$. Note
that joining two stars at their centers yields a bipartite graph consisting of
the rays of the former stars. Thus $C_{uv}$ is bipartite, and by 2 every
embedding respects the cut of the bipartition. Thus, we can split
$\mathcal{E}^{\prime}$ and obtain a valid embedding of $I^{\ast}$.

As the operation affects exactly the edges incident to $u$ and $v$ and
potentially creates a new structure with size proportional to their number,
its running time is linear in the degree of the affected pipe. ∎

Observe that this operation replaces a pipe and two cut-vertices by smaller
pipes and smaller cut-vertices, respectively. Through multiple applications of
EncapsulateAndJoin we can thus step by step decrease the degree of cut-vertex-
to-cut-vertex pipes, until there are none left in the instance.

###  3.3 The PropagatePQ Operation

The operation PropagatePQ communicates embedding restrictions of a biconnected
component across a pipe. These restrictions are represented by the embedding
tree of the matched P-vertex of interest. Both endpoints of the pipe are
replaced by copies of this tree. To ensure that both copies are embedded in a
compatible way, we synchronize their inner nodes using pipes and
Q-constraints; see Figure 4.

(a)

(b)

Figure 4: A block-vertex $u$ matched with vertex $v$ (a); the bijection
$\varphi_{uv}$ between the incident edges is shown as follows: the bold edge
of $u$ is mapped to the bold edge of $v$, the remaining edges are mapped
according to their order, clockwise around $u$ and counter-clockwise around
$v$. The result of applying PropagatePQ $(u,I)$ (b). Note that the second
inserted tree $T_{u}^{\prime}$ is mirrored with respect to $T_{u}$.

For an instance $I=(G,\mathcal{P},\mathcal{Q},\psi)$ of Synchronized
Planarity, let $u$ be a block-vertex matched by a pipe
$\rho=(u,v,\varphi_{uv})$. If the embedding tree $\mathcal{T}_{u}$ of $u$ is
non-trivial (i.e., not only consists of a single P-node), then the operation
PropagatePQ $(u,I)$ can be applied, resulting in an instance
$I^{\prime}=(G^{\prime},\mathcal{P}^{\prime},\mathcal{Q}^{\prime},\psi^{\prime})$
as follows. We turn the PQ-tree $\mathcal{T}_{u}$ into a tree $T_{u}$ by
interpreting Q-nodes as Q-vertices and P-nodes as P-vertices. To construct
$G^{\prime}$ from $G$, we replace $u$ with $T_{u}$ by reconnecting the
incident edges of $u$ to the respective leaves of $T_{u}$. We also replace $v$
by a second copy $T_{u}^{\prime}$ of $T_{u}$ by reconnecting an edge $e$
incident to $v$ to the leaf of $T_{u}^{\prime}$ that corresponds to
$\varphi_{vu}(e)$. For a vertex $\alpha$ of $T_{u}$ we denote the
corresponding vertex of $T_{u}^{\prime}$ by $\alpha^{\prime}$. For an edge
$\alpha\beta$ of $T_{u}$ we define
$\varphi_{T_{u}T_{u}^{\prime}}(\alpha\beta)=\alpha^{\prime}\beta^{\prime}$.
For each Q-vertex $\alpha$ of $T_{u}$, we define $\psi^{\prime}(\alpha)$
according to the rotation of the corresponding Q-node in $\mathcal{T}_{u}$.
For the Q-vertex $\alpha^{\prime}$ of $T_{u}^{\prime}$, we define
$\psi^{\prime}(\alpha^{\prime})=\overline{\varphi_{T_{u}T_{u}^{\prime}}(\psi^{\prime}(\alpha))}$.
For all other Q-vertices of $I$, $\psi^{\prime}$ coincides with $\psi$. We
define the partition
$\mathcal{Q}^{\prime}=\mathcal{Q}\cup\left\\{\\{\alpha,\alpha^{\prime}\\}\mid\alpha\text{
is a Q-vertex of }T_{u}\right\\}$. For each P-vertex $\alpha$ of $T_{u}$, we
define a pipe
$\rho_{\alpha}=(\alpha,\alpha^{\prime},\varphi_{\alpha\alpha^{\prime}})$ with
$\varphi_{\alpha\alpha^{\prime}}(e)=\varphi_{T_{u}T_{u}^{\prime}}(e)$ for each
edge $e$ incident to $\alpha$. Finally, we define the matching
$\mathcal{P}^{\prime}=(\mathcal{P}\setminus\\{\rho\\})\cup\left\\{\rho_{\alpha}\mid\alpha\text{
is a P-vertex of }T_{u}\right\\}$.

######  Lemma 5.

Applying PropagatePQ to a block-vertex $u$ with a non-trivial embedding tree
yields an equivalent instance. If the embedding tree $\mathcal{T}_{u}$ is
known, operation PropagatePQ runs in $O(\operatorname{deg}(u))$ time.

###### Proof.

First we show that PropagatePQ preserves a valid embedding $\mathcal{E}$ of
$I$. To define an embedding $\mathcal{E}^{\prime}$ for $I^{\prime}$, we
substitute $u$ and $v$ in $\mathcal{E}$ by suitably embedded trees $T_{u}$ and
$T_{u}^{\prime}$. The tree inserted at $u$ represents all the possible
rotations of $u$, including $\mathcal{E}(u)$ and the insertion can therefore
be done without introducing crossings. As $\mathcal{E}$ fulfilled the
P-constraint of the pipe $uv$, we know that
$\mathcal{E}(u)=\overline{\varphi_{vu}(\mathcal{E}(v))}$. Therefore, the same
holds for inserting the mirrored copy $T_{u}^{\prime}$ of $T_{u}$ instead of
$v$. Thus, the resulting embedding $\mathcal{E}^{\prime}$ is planar. Note
that, the mirror embedding of $T_{u}$ is obtained by reversing the rotation of
each inner vertex of $T_{u}$. Therefore, for each inner vertex $\alpha$ of
$T_{u}$ it holds that
$\mathcal{E}^{\prime}(\alpha)=\overline{\varphi_{\alpha^{\prime}\alpha}(\mathcal{E}^{\prime}(\alpha^{\prime}))}$.
Thus, all the new pipes are satisfied. Similarly, for each inner Q-vertex
$\alpha$ of $T_{u}$ the rotation in $\mathcal{E}^{\prime}$ is either
$\psi^{\prime}(\alpha)$ or $\overline{\psi^{\prime}(\alpha)}$. As the rotation
of $\alpha^{\prime}$ in $\mathcal{E}^{\prime}$ is mirrored, the new
Q-constraints are satisfied. Since all other P- and Q-constraints remain
satisfied, $\mathcal{E}^{\prime}$ is a valid embedding for $I^{\prime}$.

Conversely, assume that $\mathcal{E}^{\prime}$ is a valid embedding for
$I^{\prime}$. We obtain an embedding $\mathcal{E}$ of $I$ by contracting
$T_{u}$ and $T_{v}$ into single vertices $u$ and $v$, respectively. Clearly,
$\mathcal{E}$ is a planar embedding. All Q-constraints of $I$ and also all
pipes except for $\rho$ clearly remain satisfied. It remains to show that also
pipe $\rho$ is satisfied. For each vertex $\alpha$ of $T_{u}$ it holds that
$\mathcal{E}^{\prime}(\alpha)=\overline{\varphi_{\alpha^{\prime}\alpha}(\mathcal{E}^{\prime}(\alpha^{\prime}))}$,
as $\mathcal{E}^{\prime}$ in particular fulfills all new Q- and P-constraints
of $I^{\prime}$. Therefore, the circular order of the leaves of $T_{u}$ is the
reverse of the order of the leaves of $T_{u}^{\prime}$. This means that
$\mathcal{E}(u)=\overline{\varphi_{vu}(\mathcal{E}(v))}$, that is, $\rho$ is
satisfied.

This concludes the proof of correctness of PropagatePQ. As the operation
affects exactly the edges incident to $u$ and $v$, its running time is linear
in the degree of the affected node, given the embedding tree $\mathcal{T}_{u}$
is known. ∎

Observe that since we assume that $\mathcal{T}_{u}$ is non-trivial, the
degrees of all vertices in $T_{u}$ and $T_{u}^{\prime}$ are strictly smaller
than the degree of $u$. Thus, by repeatedly applying the PropagatePQ
operation, we eventually arrive at an equivalent instance where all matched
block-vertices have a trivial embedding tree.

###  3.4 The SimplifyMatching Operation

The remaining operation is SimplifyMatching, which is used to resolve pipes
where one side has no restrictions to be communicated to the other side. This
is the case when one of the two matched vertices is a pole of a bond that
allows arbitrary rotation. We distinguish three cases: i) bonds where one pole
can always mimic the rotation of the other, ii) bonds where the pipe
synchronizes one pole with the other (similar to the toroidal instances of
Fulek and Tóth [18]), and iii) bonds that link two distinct pipes.

For an instance $I=(G,\mathcal{P},\mathcal{Q},\psi)$ of Synchronized
Planarity, let $u$ be a block-vertex of $G$ whose embedding tree is trivial
and that is matched by a pipe $\rho$. Then, its embedding is determined by
exactly one triconnected component $\mu$, which is a bond [7]. Thus $u$ is the
pole of bond $\mu$, and we call the vertex $v$ that is the other pole of $\mu$
the _partner_ of $u$. If $v$ is either unmatched or a block-vertex with
trivial embedding tree, the operation SimplifyMatching $(u,I)$ can be applied,
resulting in an instance
$I^{\prime}=(G^{\prime},\mathcal{P}^{\prime},\mathcal{Q}^{\prime},\psi^{\prime})$
as follows.

  1. (i)

If $v$ is an unmatched P-vertex as shown in Figure 5(a), $I^{\prime}$ is
obtained from $I$ by removing $\rho$.

  2. (ii)

If $\rho$ matches $u$ with $v$, it connects the two poles of the bond $\mu$,
as shown in Figure 5(b). The pipe requires both $u$ and $v$ to have the same
degree and as $u$ has a trivial embedding tree, $v$ also has a trivial
embedding tree. The rotation of the vertices is thus exclusively determined by
the embedding of the bond and there are bijections $\delta_{u}$ and
$\delta_{v}$ between the edges incident to $u$ and $v$, respectively, and the
virtual edges within the bond. We now check that these bijections are
compatible with the bijection $\varphi_{uv}$ given by the pipe. Let
$\delta_{vu}=\delta_{u}^{-1}\circ\delta_{v}$ be a bijection between the edges
incident to $v$ and the edges incident to $u$, and let
$\pi=\varphi_{uv}\circ\delta_{vu}$ be a permutation of the edges incident to
$v$. If all cycles of $\pi$ have the same length, $I^{\prime}$ is obtained
from $I$ by removing $\rho$. Otherwise $I^{\prime}$ is a trivial no-instance,
e.g., having $G^{\prime}=K_{5}$.

  3. (iii)

If $v$ is matched with a P-vertex $v^{\prime}\neq u$ via pipe
$\rho^{\prime}=(v,v^{\prime},\varphi_{vv^{\prime}})$, let $u^{\prime}$ be the
other endpoint of $\rho=(u,u^{\prime},\varphi_{uu^{\prime}})$. We remove
$\rho$ and $\rho^{\prime}$ and add the new pipe
$\rho^{*}=(u^{\prime},v^{\prime},\varphi_{u^{\prime}v^{\prime}})$ with
$\varphi_{u^{\prime}v^{\prime}}=\varphi_{vv^{\prime}}\circ\delta_{uv}\circ\varphi_{u^{\prime}u}$;
see Figure 5(c).

(a)

(b)

(c)

Figure 5: The three cases of the SimplifyMatching operation. In Item i (a) and
Item ii (b), the pipe $\rho$ is removed. In Item iii (c) the pipes
$\rho,\rho^{\prime}$ are replaced by pipe $\rho^{\star}$.

######  Lemma 6.

Applying SimplifyMatching to a vertex $u$ with a trivial embedding tree yields
an equivalent instance in $O(\operatorname{deg}(u))$ time.

###### Proof.

First we show that if $\mathcal{E}$ is a valid embedding of $I$, then it is
also a valid embedding of $I^{\prime}$. This clearly holds if $I^{\prime}$ is
obtained from $I$ by removing a pipe, as in Item i.

It remains to investigate Item ii and Item iii. In the latter case, let
$u^{\prime}$ be the vertex to which $u$ is matched and let $v^{\prime}\neq u$
be the vertex to which $v$ is matched. We want to show that $\mathcal{E}$
satisfies the constraint
$\mathcal{E}(v^{\prime})=\overline{\varphi_{u^{\prime}v^{\prime}}(\mathcal{E}(u^{\prime}))}$
of the newly added pipe
$\rho^{*}=(u^{\prime},v^{\prime},\varphi_{u^{\prime}v^{\prime}})$. By
assumption the pipes $\rho,\rho^{\prime}$ are satisfied by $\mathcal{E}$, that
is $\mathcal{E}(u)=\overline{\varphi_{u^{\prime}u}(\mathcal{E}(u^{\prime}))}$
and
$\mathcal{E}(v^{\prime})=\overline{\varphi_{vv^{\prime}}(\mathcal{E}(v))}$.
Moreover, as both $u$ and $v$ have a trivial embedding tree, the bijections
$\delta_{u},\delta_{v}$ are defined as above. Thus
$\delta_{u}(\mathcal{E}(u))$ and $\delta_{v}(\mathcal{E}(v))$ define a
circular orders of the virtual edges of $\mu$. Since the embedding is planar,
$\delta_{u}(\mathcal{E}(u))=\overline{\delta_{v}(\mathcal{E}(v))}$. This
yields $\mathcal{E}(v)=\overline{\delta_{uv}(\mathcal{E}(u))}$ and thus

$\displaystyle\mathcal{E}(v^{\prime})$
$\displaystyle=\overline{\varphi_{vv^{\prime}}(\overline{\delta_{uv}(\mathcal{E}(u))})}=\varphi_{vv^{\prime}}(\delta_{uv}(\mathcal{E}(u)))$
$\displaystyle=\varphi_{vv^{\prime}}(\delta_{uv}(\overline{\varphi_{u^{\prime}u}(\mathcal{E}(u^{\prime}))}))=\overline{\varphi_{vv^{\prime}}\circ\delta_{uv}\circ\varphi_{u^{\prime}u}(\mathcal{E}(u^{\prime}))}=\overline{\varphi_{u^{\prime}v^{\prime}}(\mathcal{E}(u^{\prime}))}\,.$

In particular, this means that $\rho^{*}$ is satisfied and therefore
$\mathcal{E}$ is valid.

In Item ii, we consider the above permutation $\pi$. Analogously to
$\mathcal{E}(v)=\overline{\delta_{uv}(\mathcal{E}(u))}$, it is
$\mathcal{E}(u)=\overline{\delta_{vu}(\mathcal{E}(v))}$, and since
$\mathcal{E}$ satisfies $\rho$, we find that
$\pi(\mathcal{E}(v))=\varphi_{uv}\circ\delta_{vu}(\mathcal{E}(v))=\varphi_{uv}(\overline{\mathcal{E}(u)})=\mathcal{E}(v)$.
All cycles of $\pi$ have the same length [7, Lemma 2.1] and therefore
$I^{\prime}$ is obtained from $I$ by removing $\rho$ and, in particular,
$\mathcal{E}$ is a valid embedding of $I^{\prime}$.

Conversely, assume that $\mathcal{E}^{\prime}$ is a valid embedding for
$I^{\prime}$. To obtain a valid embedding $\mathcal{E}$ of $I$, we modify the
embedding $\mathcal{E}^{\prime}$ by changing the order of the virtual edges of
the bond $\mu$ with poles $u$ and $v$ in such a way that the removed pipes are
satisfied. Since, compared to $\mathcal{E}^{\prime}$, we only change the
embedding of a bond, $\mathcal{E}$ is guaranteed to be planar. The details
depend on which case of the operation applies.

If $v$ is unmatched in $I$, we change the embedding of $\mu$ such that
$\mathcal{E}(u)=\overline{\varphi_{u^{\prime}u}(\mathcal{E}(u^{\prime}))}$.
This is possible since there is a bijection between the edges incident to $u$
and the virtual edges of $\mu$. The new embedding $\mathcal{E}$ satisfies
$\rho$ and, since $v$ is unmatched, also all other pipes of $I$ remain
satisfied.

In Item ii, $v$ is matched with $u$ and we consider the above permutation
$\pi$. As $\mathcal{E}^{\prime}$ is a valid embedding, $I^{\prime}$ results
from $I$ by removing $\rho$ and we know that all cycles of $\pi$ have the same
length. There exists a circular ordering $\sigma$ of the edges incident to $v$
with $\pi(\sigma)=\sigma$ [7, Lemma 2.1]. We change the embedding of $\mu$
such that $\mathcal{E}(v)=\sigma$ and, to retain planarity,
$\mathcal{E}(u)=\overline{\delta_{vu}(\mathcal{E}(v))}$. This satisfies $\rho$
as
$\overline{\varphi_{uv}(\mathcal{E}(u))}=\overline{\varphi_{uv}(\overline{\delta_{vu}(\mathcal{E}(v))}}={\varphi_{uv}({\delta_{vu}(\mathcal{E}(v))}}=\pi(\mathcal{E}(v))=\mathcal{E}(v)$
and thus $\mathcal{E}$ is valid.

In Item iii, $v$ is matched with $v^{\prime}\neq u$. We obtain $\mathcal{E}$
from $\mathcal{E}^{\prime}$ by setting
$\mathcal{E}(u)=\overline{\varphi_{u^{\prime}u}(\mathcal{E}(u^{\prime}))}$ and
$\mathcal{E}(v)=\overline{\varphi_{v^{\prime}v}(\mathcal{E}(v^{\prime}))}$.
This satisfies $\rho$ and $\rho^{\prime}$, and to verify the planarity of
$\mathcal{E}$ it suffices to show that
$\mathcal{E}(v)=\overline{\delta_{uv}(\mathcal{E}(u))}$. Since $\rho^{*}$ is
satisfied by $\mathcal{E}^{\prime}$ and $\mathcal{E}$ differs from
$\mathcal{E}^{\prime}$ only at $u$ and $v$, we know that
$\mathcal{E}(v^{\prime})=\overline{\varphi_{u^{\prime}v^{\prime}}(\mathcal{E}(u^{\prime}))}=\overline{\varphi_{vv^{\prime}}\circ\delta_{uv}\circ\varphi_{u^{\prime}u}(\mathcal{E}(u^{\prime}))}$.
This is equivalent to
$\varphi_{v^{\prime}v}(\mathcal{E}(v^{\prime}))=\overline{\delta_{uv}(\varphi_{u^{\prime}u}(\mathcal{E}(u^{\prime})))}$.
By the definitions of $\mathcal{E}(u)$ and $\mathcal{E}(v)$, this yields
$\mathcal{E}(v)=\overline{\delta_{uv}(\mathcal{E}(u))}$, that is $\mathcal{E}$
is planar.

This concludes the proof of correctness of SimplifyMatching. The updates to
the matching $\mathcal{P}$ can be done in constant time, while the updates to
the bijection $\varphi$ and the check for cycle lengths require
$O(\operatorname{deg}(u))$ time. ∎

###  3.5 Reduced and Pipe-Free Instances

With our exposition of the fundamental operations complete, we now study how
to solve instances where none of those operations can be applied. We call such
instances _reduced_.

######  Lemma 7.

An instance of Synchronized Planarity is reduced if and only if it contains no
pipes.

###### Proof.

Obviously, a pipe-free instance is reduced. Conversely, consider a reduced
instance $I$. Assume, for the sake of contradiction, that $I$ contains a pipe.
We now show that this implies that one of the operations is applicable, i.e.,
$I$ is not reduced.

Assume that $I$ contains no matched cut-vertices and thus all matched vertices
are block-vertices. If there is a matched P-vertex with a non-trivial
embedding tree, PropagatePQ can be applied. Otherwise, all matched P-vertices
are block-vertices with trivial PQ-trees and SimplifyMatching can be applied
to an arbitrary endpoint of a pipe. This contradicts the assumption that $I$
is reduced, and thus $I$ must contain a matched cut-vertex.

Now let $u$ be a matched cut-vertex of maximum degree that is matched to a
vertex $v$ by a pipe $\rho$. If $v$ is also a cut-vertex, we can apply
EncapsulateAndJoin. If $v$ is a block-vertex with a non-trivial embedding
tree, we can apply PropagatePQ. Therefore, $v$ must be a block-vertex with a
trivial PQ-tree. Now we can apply SimplifyMatching, unless the partner
$v^{\prime}$ of $v$ is a matched cut-vertex. This is however excluded, since
$\deg(u)=\deg(v)<\deg(v^{\prime})$, contradicting the maximality of $\deg(u)$.
The last inequality follows from the fact that $\deg(v)\leq\deg(v^{\prime})$
already holds in the block of $G$ that contains $v$ and $v^{\prime}$, but as
$v^{\prime}$ is a cut-vertex, it has at least one neighbor outside that block.
∎

To solve instances without pipes in linear time, note that a planar embedding
of such an instance is valid if and only if it satisfies the Q-constraints. As
Q-vertices only have a binary choice for their rotation, it is relatively easy
to synchronize them via a 2-SAT formula. Linear-time algorithms follow from,
e.g., [7], and can also be obtained from techniques similar to those used by
Fulek and Tóth [18] for cubic graphs. For the sake of completeness, we present
a self-contained solution.

######  Lemma 8.

An instance of Synchronized Planarity without pipes can be solved in $O(m)$
time. A valid embedding can be computed in the same time, if it exists.

###### Proof.

We replace each Q-vertex by a wheel of the respective degree. Note that each
such wheel is biconnected and entirely contained in its rigid triconnected
component. We now use the decomposition in triconnected components to
represent all possible planar embeddings. As the wheel-replacements yield an
instance that is linear in the size of the initial instance, this
decomposition can be done in $O(m)$ time. If at least one of the rigids has no
planar embedding, abort and report a non-planar instance. It remains to
restrict the possible embeddings of the rigids so that all Q-constraints are
satisfied.

We construct an instance of 2-SAT, where each solution corresponds to a planar
embedding $\mathcal{E}$ that is a valid solution for $I$. For every Q-vertex
$v$ the boolean variable $x_{v}$ is true if the rotation of $v$ in
$\mathcal{E}$ is equal to the default rotation of $v$ (i.e. if
$\mathcal{E}(v)=\psi(v)$). Additionally, for every Q-constraint cell
$Q\in\mathcal{Q}$ we add a boolean variable $x_{Q}$, and for every Q-vertex
$v\in Q$ we add the constraint $(x_{v}\vee\neg x_{Q})\wedge(\neg x_{v}\vee
x_{Q})$. This ensures that the rotations of the Q-vertices are consistent
within their cell and thus satisfy the Q-constraints. We still need to ensure
that the 2-SAT instance allows only planar embeddings. For each rigid $\mu$,
we fix one of its two planar embeddings as its default embedding
$\mathcal{E}_{\mu}$ and add another boolean variable $x_{\mu}$, indicating
whether $\mathcal{E}_{\mu}$ or $\overline{\mathcal{E}_{\mu}}$ shall be used in
$\mathcal{E}$. Due to the wheel replacement, each Q-vertex $v$ is entirely
contained in its rigid $\mu$, which can be found in constant time using one of
the incident edges. For every Q-vertex $v$ we now add one of the following two
constraints with regard to its rigid $\mu$: either 1) $(x_{v}\vee\neg
x_{\mu})\wedge(\neg x_{v}\vee x_{\mu})$ if $\psi(v)=\mathcal{E}_{\mu}(v)$, or
2) $(x_{v}\vee x_{\mu})\wedge(\neg x_{v}\vee\neg x_{\mu})$ if
$\psi(v)=\overline{\mathcal{E}_{\mu}(v)}$. This ensures that the rotation of
every Q-vertex is consistent with the planar embedding of its rigid.

In the resulting 2-SAT instance, we have a boolean variable for each Q-vertex,
Q-constraint and rigid, and two constraints for each Q-vertex. The constructed
2-SAT formula thus has size in $O(m)$ and can be solved in linear time. If it
has no solution, we report an invalid instance and abort. Otherwise, we can
use $x_{\mu}$ to decide whether $\mathcal{E}_{\mu}$ should be mirrored or not.
Choosing a planar embedding for each bond, i.e. a permutation of the parallel
virtual edges between the two poles, this yields a valid planar embedding
$\mathcal{E}$ that is a valid solution for $I$. ∎

###  3.6 Finding a Reduced Instance

As mentioned above, we exhaustively apply the operations EncapsulateAndJoin,
PropagatePQ, and SimplifyMatching. We claim that this algorithm terminates and
yields a reduced instance after a polynomial number of steps. The key idea is
that the operations EncapsulateAndJoin, PropagatePQ and SimplifyMatching
always make progress by either reducing the number of pipes, or by splitting
pipes into pipes of smaller degree. This suggests that, eventually, we arrive
at an instance without pipes. However, there are two caveats. First, the
encapsulation in the first step of EncapsulateAndJoin creates new pipes and
thus has the potential to undo progress. Second, the smaller pipes resulting
from splitting a pipe with PropagatePQ might cause further growth of the
instance, potentially causing a super-polynomial number of steps.

We resolve both issues by using a more fine-grained measure of progress in the
form of a potential function. To overcome the first issue, we show that for
each application of EncapsulateAndJoin, the progress that is undone in the
first step is outweighed by the progress made through the following join in
the second step. Similarly, for the second issue, we show that the sum of the
parts is no bigger than the whole when splitting pipes.

As P-vertices of degree 3 or less are converted to Q-vertices (see Section
3.1.1), we use
$\operatorname{deg*}(u)=\operatorname{deg*}(v)=\operatorname{deg*}(\rho)=\max\\{\operatorname{deg}(x)-3,0\\}$
to denote the number of incident edges that keep a P-vertex $u$ (and also the
other endpoint $v$ of its pipe $\rho=(u,v,\varphi_{uv})$) from becoming
converted to a Q-vertex. We also partition the set of all pipes $\mathcal{P}$
into the two cells $\mathcal{P}_{CC}$ and
$\mathcal{P}_{B}=\mathcal{P}\setminus\mathcal{P}_{CC}$, where
$\mathcal{P}_{CC}$ contains all pipes where both endpoints are cut-vertices.

######  Definition 9.

For an instance $I$ we define its potential as
$\Phi(I)=\sum_{\rho\in\mathcal{P}_{B}}\operatorname{deg*}(\rho)+\sum_{\rho\in\mathcal{P}_{CC}}(2\operatorname{deg*}(\rho)-1)$.

We show that the operations always decrease this potential. To analyze the
potential change of PropagatePQ and EncapsulateAndJoin, we need the following
technical lemma for bounding the sum of the degrees of multiple smaller pipes
replacing a single bigger pipe.

######  Lemma 10.

Let $k\geq 2,\,d_{1}\geq d_{2}\geq\ldots\geq d_{k}\geq 1$ and $c\geq 0$ be
integers. Let $j=\max\left\\{i\mid d_{i}\geq 3\right\\}$ and let
$\ell=\left|\left\\{i\mid d_{i}=2\right\\}\right|$. If $3\leq c+\ell+2j$, then
$k+\sum_{i=1}^{k}\max\\{d_{i}-3,0\\}\leq c-3+\sum_{i=1}^{k}d_{i}$. If
$4\leq\sum_{i=1}^{k}d_{i}$, then
$\sum_{i=1}^{k}\max\\{d_{i}-3,0\\}\leq-4+\sum_{i=1}^{k}d_{i}$.

###### Proof.

Observe that the $d_{i}$ are ordered increasing and thus $d_{i}\geq 3$ for
$i=1,\dots,j$ and $d_{i}<3$ for $i=j+1,\dots,k$. More specifically, it is
$d_{j+1},\ldots,d_{j+\ell}=2$ and $d_{j+\ell+1},\ldots,d_{k}=1$. This yields
$\sum_{i=j+1}^{j+\ell}d_{i}=2\cdot\ell$ and
$\sum_{i=j+\ell+1}^{k}d_{i}=k-\ell-j$ and we can also avoid the “$\max$” using
$\sum_{i=1}^{k}\max\\{d_{i}-3,0\\}=\sum_{i=1}^{j}(d_{i}-3)=-3j+\sum_{i=1}^{j}d_{i}$.
We now start at $3\leq c+\ell+2j$, which can be rewritten as $k-3j\leq
c-3+2\ell+(k-\ell-j)$. Adding $\sum_{i=1}^{j}d_{i}$ on both sides and using
the above observations yields

$k+\sum_{i=1}^{k}\max\\{d_{i}-3,0\\}=k-3j+\sum_{i=1}^{j}d_{i}\leq
c-3+\sum_{i=j+1}^{j+\ell}d_{i}+\sum_{i=j+\ell+1}^{k}d_{i}+\sum_{i=1}^{j}d_{i}=c-3+\sum_{i=1}^{k}d_{i}.$

Note that inserting $c=k-1$ in the first formula yields the second formula. It
remains to show that in this case $3\leq c+\ell+2j$ or the equivalent $4\leq
k+\ell+2j$ follow from $4\leq\sum_{i=1}^{k}d_{i}$. If $k\geq 4$, the
inequality obviously always holds. If $k=3$, it must be $j>1$ or $\ell>1$ as
the sum is at least 4. If $k=2$, it must be $j>1$ or $\ell\geq 2$ as the sum
is at least 4. ∎

######  Lemma 11.

For an instance $I=(G,\mathcal{P},\mathcal{Q},\psi)$ of Synchronized Planarity
and an instance
$I^{\prime}=(G^{\prime},\mathcal{P}^{\prime},\mathcal{Q}^{\prime},\psi^{\prime})$
that results from application of either EncapsulateAndJoin, PropagatePQ or
SimplifyMatching to $I$, the following three properties hold:

  1. (i)

The potential reduction $\Delta\Phi=\Phi(I)-\Phi(I^{\prime})$ is at least 1.

  2. (ii)

The number of nodes added to the graph satisfies $\Delta
V=|V(G^{\prime})|-|V(G)|\leq 2\cdot\Delta\Phi+12$.

  3. (iii)

If the operation replaces a connected component $C$ by one or multiple
connected components, then each such component $C^{\prime}$ satisfies $\Delta
E(C)=|E(C^{\prime})|-|E(C)|\leq 2\cdot\Delta\Phi$.

###### Proof.

We now analyze the effects of EncapsulateAndJoin, PropagatePQ, and
SimplifyMatching on the measures $\Delta\Phi$, $\Delta V$ and $\Delta E(C)$
and show that the found changes satisfy the claimed bounds.

Operation EncapsulateAndJoin $(\rho,I)$ in the first step encapsulates both
cut-vertices $u,v$ to their own multi-star components. For each block incident
to $u$, this introduces two new vertices that are connected by a new pipe. Let
$d_{1}\geq d_{2}\geq\ldots\geq d_{k-1}\geq d_{k}\geq 1$ be the degrees of the
$k\geq 2$ rays of $u$ after the encapsulation. As one end of the added pipes
is a block-vertex, the potential is increased by
$\sum_{i=1}^{k}\max\\{d_{i}-3,0\\}$. The rays around $v$ increase the
potential and number of vertices likewise, where $d_{1}^{\prime}\geq
d_{2}^{\prime}\geq\ldots\geq d_{k^{\prime}-1}^{\prime}\geq
d_{k^{\prime}}^{\prime}\geq 1$ are the degrees of the $k^{\prime}\geq 2$ rays
of $v$ after the encapsulation. Using
$\sum_{i=1}^{k}d_{i}=\sum_{i=1}^{k^{\prime}}d_{i}^{\prime}=D$ it is
$\operatorname{deg}(\rho)=\operatorname{deg}(v)=\operatorname{deg}(u)=D$ and
$\operatorname{deg*}(\rho)=\operatorname{deg*}(v)=\operatorname{deg*}(u)=\max\\{D-3,0\\}=D-3$
as $u$ and $v$ are P-vertices of the same degree greater then three. In the
second step, removing $\rho$ connecting two cut-vertices together with its
endpoints reduces the potential by $2\operatorname{deg*}(\rho)-1$ and we thus
get

$\Delta\Phi\ =\ 2\cdot\left(D-3\right)-1\ -\sum_{i=1}^{k}\max\\{d_{i}-3,0\\}\
-\sum_{i=1}^{k^{\prime}}\max\\{d_{i}^{\prime}-3,0\\}.$

As $D\geq 4$, we know from the second formula of 10 that
$\sum_{i=1}^{k}\max\\{d_{i}-3,0\\}\leq(\sum_{i=1}^{k}d_{i})-4=D-4$ and also
$\sum_{i=1}^{k^{\prime}}\max\\{d_{i}^{\prime}-3,0\\}\leq D-4$. Using this
inequality in the formula above yields
$\Delta\Phi=2D-7-\sum_{i=1}^{k}\max\\{d_{i}-3,0\\}-\sum_{i=1}^{k^{\prime}}\max\\{d_{i}^{\prime}-3,0\\}\geq
2D-7-(D-4)-(D-4)=1$ as claimed by (i).

As the encapsulation generates two vertices for each ray and the join removes
two vertices, we have $\Delta V=2k+2k^{\prime}-2$. 10 with $c=3$
unconditionally yields $k\leq D-\sum_{i=1}^{k}\max\\{d_{i}-3,0\\}$ and
$k^{\prime}\leq D-\sum_{i=1}^{k^{\prime}}\max\\{d_{i}^{\prime}-3,0\\}$. Now
claim (ii) holds as

$\Delta V\leq
2\cdot\left(D-\sum_{i=1}^{k}\max\\{d_{i}-3,0\\}+D-\sum_{i=1}^{k^{\prime}}\max\\{d_{i}^{\prime}-3,0\\}-1\right)=2\cdot\left(\Delta\Phi+6\right).$

In the first step of EncapsulateAndJoin, two new components with
$\operatorname{deg}(u)=\operatorname{deg}(v)$ edges each are added, which are
then pairwise combined in the second step, yielding a new component with
$\sum_{i=1}^{k}d_{i}=\sum_{i=1}^{k^{\prime}}d_{i}^{\prime}$ edges, which is no
bigger than the components of $u$ or $v$ as required for (iii).

Operation PropagatePQ $(u,I)$ replaces the pipe $\rho$ having block-vertex $u$
as one endpoint by one pipe for each inner P-node of the embedding tree
$\mathcal{T}_{u}$ of $u$. Let $d_{1}\geq d_{2}\geq\ldots\geq d_{k-1}\geq
d_{k}$ be the degrees of the $k\geq 2$ inner vertices of the non-trivial
$\mathcal{T}_{u}$. The tree $\mathcal{T}_{u}$ has $\operatorname{deg}(u)$
leaves and thus
$(\sum_{i=1}^{k}d_{i})+\operatorname{deg}(u)=2\cdot|E(\mathcal{T}_{u})|=2\cdot(|V(\mathcal{T}_{u})|-1)=2\cdot(k+\operatorname{deg}(u)-1)$
or, equivalently,
$\operatorname{deg}(u)=\left(\sum_{i=1}^{k}(d_{i}-2)\right)+2$. As $u$ is a
P-vertex with degree at least 4,
$\operatorname{deg*}(u)=\operatorname{deg}(u)-3=\left(\sum_{i=1}^{k}(d_{i}-2)\right)-1$.
As $\mathcal{T}_{u}$ contains no vertices of degree 2, it is $d_{i}\geq 3$ for
$i=1,\ldots,k$. As the added pipes all have one endpoint in the biconnected
component of $u$, the potential is reduced by
$\Delta\Phi=\operatorname{deg*}(u)-\sum_{i=1}^{k}\max\\{d_{i}-3,0\\}=\left(\sum_{i=1}^{k}(d_{i}-2)\right)-1-\left(\sum_{i=1}^{k}(d_{i}-3)\right)=k-1\geq
1$, which shows (i).

Moreover, we replace the two endpoints of $\rho$ each by the inner nodes of
$\mathcal{T}_{u}$, yielding $\Delta V=2k-2$ additional nodes. Note that
$\Delta V=2k-2=2\cdot\Delta\Phi<2\cdot\Delta\Phi+12$ as claimed by (ii). As
each inner node except for the root has one edge connecting it to its parent,
we also add $\Delta E(C)=k-1$ additional edges to each component. Observe that
$\Delta E(C)=k-1<2k-2=2\cdot\Delta\Phi$ as claimed by (iii).

Operation SimplifyMatching always removes at least one pipe
$\rho\in\mathcal{P}_{B}$ and thus decreases the potential by at least
$\operatorname{deg*}(\rho)$. If two pipes $\rho,\rho^{\prime}$ are replaced by
their transitive shortcut (i.e. Item iii of SimplifyMatching applies), this
adds a new pipe $\rho^{*}$. If at least one endpoint of $\rho^{*}$ is a block-
vertex, the potential change is
$\Delta\Phi=2\operatorname{deg*}(\rho)-\operatorname{deg*}(\rho)$. Otherwise,
both endpoints are cut-vertices and $\rho^{*}$ belongs to $\mathcal{P}_{CC}$,
yielding a potential change of
$\Delta\Phi=2\operatorname{deg*}(\rho)-(2\operatorname{deg*}(\rho)-1)=1$. As
no vertices or edges are added or removed $\Delta V=\Delta E(C)=0$, which is
less than $\Delta\Phi$. ∎

With this lemma, we know that each step decreases the potential by at least 1
without growing the graph too much. The following shows an upper bound on the
potential.

######  Lemma 12.

Let $I$ be an instance of Synchronized Planarity. Then, $\Phi(I)<2m$.

###### Proof.

Each pipe $\rho$ matching two vertices $u$ and $v$ contributes at most
$2\operatorname{deg*}(\rho)-1<\deg(u)+\deg(v)$ to the potential. Since each
vertex is part of at most one pipe, the sum of all potentials is bounded by
$\sum_{v\in V}\deg(v)=2m$. ∎

This can be used to bound the size of instances resulting from applying
multiple operations consecutively and finally to bound the time required to
find a solution for an instance.

######  Theorem 12.

Synchronized Planarity can be solved in $O(m^{2})$ time.

###### Proof.

By 11 the potential function decreases with each applied operation. Therefore,
by Lemma 12, after $k\leq 2m$ operations a reduced instance
$I^{\prime}=(G^{\prime},\mathcal{P}^{\prime},\mathcal{Q}^{\prime},\psi^{\prime})$
is reached. We claim that the resulting graph
$G^{\prime}=(V^{\prime},E^{\prime})$ has
$|V^{\prime}|\leq|V|+4\cdot|E|+12\cdot k$ vertices and each connected
component $C^{\prime}$ of $G^{\prime}$ has $|E(C^{\prime})|\leq 5\cdot|E|$
edges.

Let $\Delta\Phi_{i}$ for $i\in[1,\ldots,k]$ be the potential reduction caused
by the $i$th applied operation. According to 11, this operation also added
$\Delta V_{i}\leq 2\cdot\Delta\Phi_{i}+12$ vertices to the graph. By Lemma 12
it is $\sum_{i=1}^{k}\Delta\Phi_{i}\leq\Phi(I)<2|E|$ and thus
$|V^{\prime}|=|V|+\sum_{i=1}^{k}\Delta V_{i}\leq|V|+4\cdot|E|+12\cdot k$.
Additionally, if the $i$th operation replaces a connected component $C_{i-1}$
by one or multiple connected components, then each such component $C_{i}$
satisfies $|E(C_{i})|-|E(C_{i-1})|\leq 2\cdot\Delta\Phi_{i}$. Each connected
component $C_{1}$ of the initial graph $G$ has at most $|E|$ edges. Using the
same argument as above, we obtain
$|E(C^{\prime})|=|E(C_{k})|\leq|E|+4\cdot|E|$.

As $m\in\Omega(n)$, this shows that the resulting instance has $O(m)$ vertices
and each connected component has $O(m)$ edges. Computing the embedding trees
for a single connected component can thus still be done in $O(m)$ time. Once
the PQ-trees are available, each of the $k$ operations runs in time linear in
the degree of the vertex it is applied to, which is in $O(m)$. Thus, each
operation takes $O(m)$ time and, in total, it takes $O(m^{2})$ time to reach a
reduced instance. As the size of this reduced instance is also in $O(m^{2})$,
using 8 for finding a solution for the reduced instance can be done in
$O(m^{2})$ time. ∎

##  4 Applications

We start our discussion of applications of Synchronized Planarity with the
Atomic Embeddability problem. Recall from the introduction that Atomic
Embeddability has two graphs as input. One graph represents a molecule
structure with atoms and pipes between them, the other graph is mapped onto
that structure such that edges connect vertices on a single atom or vertices
on neighboring atoms through the corresponding pipe. As observed by Fulek and
Tóth [18, Observation 1], Atomic Embeddability can be equivalently viewed as
follows. For each atom consider the graph on that atom together with, for each
incident pipe, one virtual vertex that is incident to all edges that would
normally go through this pipe to a neighboring atom. Note that each pipe has
two virtual vertices corresponding to it, one on each of its incident atoms.
Then an instance of Atomic Embeddability is positive if and only if all these
graphs can be embedded such that every pair of virtual vertices corresponding
to the same pipe have opposite rotation. This reduces Atomic Embeddability to
Synchronized Planarity.

######  Theorem 13.

Atomic Embeddability can be solved in $O(m^{2})$ time.

To reduce Clustered Planarity to Synchronized Planarity, we use the CD-tree
[9]; also see Figure 6. Each node of the CD-tree corresponds to a graph,
called its _skeleton_. Some vertices of a skeleton are _virtual vertices_.
Each virtual vertex corresponds to exactly one virtual vertex in a different
skeleton, called its _twin_ , and there is a bijection between the edges
incident to a virtual vertex and its twin. The tree structure of the CD-tree
comes from these correspondences between twins, i.e., the CD-tree has an edge
between two nodes if and only if their skeletons have virtual vertices that
are twins of each other. It is known that a clustered graph is c-planar if and
only if the skeletons of all nodes in its CD-tree can be embedded such that
every virtual vertex and its twin have opposite rotation [9, Theorem 1].444The
theorem originally requires “the same” instead of “opposite” rotations, which
is equivalent due to the tree structure. As the CD-tree has linear size and
can be computed in linear time, this yields a linear reduction from Clustered
Planarity to Synchronized Planarity.

(a)

(b)

Figure 6: An instance of Clustered Planarity (a) and its CD-tree
representation (b), where each skeleton is shown with a gray background and
the virtual vertices are shown as colored disks.

######  Theorem 14.

Clustered Planarity can be solved in $O(n^{2})$ time.

###### Proof.

We use the disjoint union of all skeletons of the CD-tree and match each
virtual vertex with its twin using a pipe. We can assume that the underlying
graph of a Clustered Planarity instance has no multi-edges and it must be
planar to be cluster-planar, thus its number of edges satisfies $m\in O(n)$
and the runtime of our algorithm is $O(n^{2})$ in this case. ∎

Another problem that investigates the enforcement of rotation constraints in
planar embeddings is Partially PQ-constrained Planarity [7]. Here, each vertex
in the graph can be annotated with a PQ-tree that limits the rotations of
(some of) its incident edges.

Figure 7: The equivalent Synchronized Planarity instance for an instance of
Partially PQ-constrained Planarity, where the PQ-tree $T^{\prime}(v_{1})$
(left) restricts the order of the edges $\\{a,\ldots,h\\}$ around the vertex
$v_{1}$ in $G$ (right). The cap-vertex $v_{1}^{\prime}$ was added together
with two degree-1 vertices.

######  Theorem 15.

Partially PQ-constrained Planarity can be solved in $O(m^{2})$ time.

###### Proof.

Instances of Partially PQ-constrained Planarity can be converted to equivalent
instances of Synchronized Planarity by first adding the PQ-trees to the graph,
converting Q-nodes to Q-vertices similarly to PropagatePQ. Afterwards, a cap-
node is added to each PQ-tree and all leaves are connected to the respective
cap-node. To be able to match the cap-nodes with the vertices in the original
graph, further degree-1 vertices are connected to the cap-vertices until their
degree matches the respective node in the original graph; see Figure 7. The
pipe then ensures that the rotation of the matched vertex is compatible with
the PQ-tree it was annotated with. Note that previous algorithms are geared
towards biconnected instances and cannot handle cut-vertices of degree more
than 5, while this approach works for general graphs. ∎

For two graphs $G^{\leavevmode\hbox to4.78pt{\vbox
to4.78pt{\pgfpicture\makeatletter\hbox{\hskip 2.38919pt\lower-2.38919pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.1892pt}{0.0pt}\pgfsys@curveto{2.1892pt}{1.20906pt}{1.20906pt}{2.1892pt}{0.0pt}{2.1892pt}\pgfsys@curveto{-1.20906pt}{2.1892pt}{-2.1892pt}{1.20906pt}{-2.1892pt}{0.0pt}\pgfsys@curveto{-2.1892pt}{-1.20906pt}{-1.20906pt}{-2.1892pt}{0.0pt}{-2.1892pt}\pgfsys@curveto{1.20906pt}{-2.1892pt}{2.1892pt}{-1.20906pt}{2.1892pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.7}{0.0}{0.0}{0.7}{-1.22499pt}{-1.57887pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$ and
$G^{\leavevmode\hbox to4.78pt{\vbox
to4.78pt{\pgfpicture\makeatletter\hbox{\hskip 2.38919pt\lower-2.38919pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.1892pt}{0.0pt}\pgfsys@curveto{2.1892pt}{1.20906pt}{1.20906pt}{2.1892pt}{0.0pt}{2.1892pt}\pgfsys@curveto{-1.20906pt}{2.1892pt}{-2.1892pt}{1.20906pt}{-2.1892pt}{0.0pt}\pgfsys@curveto{-2.1892pt}{-1.20906pt}{-1.20906pt}{-2.1892pt}{0.0pt}{-2.1892pt}\pgfsys@curveto{1.20906pt}{-2.1892pt}{2.1892pt}{-1.20906pt}{2.1892pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.7}{0.0}{0.0}{0.7}{-1.22499pt}{-1.57887pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$, SEFE is equivalent
to finding a pair of planar embeddings that induce the same (i.e. consistent)
cyclic edge orderings and the same (i.e. consistent) relative positions on
their common graph $G=G^{\leavevmode\hbox to4.78pt{\vbox
to4.78pt{\pgfpicture\makeatletter\hbox{\hskip 2.38919pt\lower-2.38919pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.1892pt}{0.0pt}\pgfsys@curveto{2.1892pt}{1.20906pt}{1.20906pt}{2.1892pt}{0.0pt}{2.1892pt}\pgfsys@curveto{-1.20906pt}{2.1892pt}{-2.1892pt}{1.20906pt}{-2.1892pt}{0.0pt}\pgfsys@curveto{-2.1892pt}{-1.20906pt}{-1.20906pt}{-2.1892pt}{0.0pt}{-2.1892pt}\pgfsys@curveto{1.20906pt}{-2.1892pt}{2.1892pt}{-1.20906pt}{2.1892pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.7}{0.0}{0.0}{0.7}{-1.22499pt}{-1.57887pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}\cap
G^{\leavevmode\hbox to4.78pt{\vbox
to4.78pt{\pgfpicture\makeatletter\hbox{\hskip 2.38919pt\lower-2.38919pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.1892pt}{0.0pt}\pgfsys@curveto{2.1892pt}{1.20906pt}{1.20906pt}{2.1892pt}{0.0pt}{2.1892pt}\pgfsys@curveto{-1.20906pt}{2.1892pt}{-2.1892pt}{1.20906pt}{-2.1892pt}{0.0pt}\pgfsys@curveto{-2.1892pt}{-1.20906pt}{-1.20906pt}{-2.1892pt}{0.0pt}{-2.1892pt}\pgfsys@curveto{1.20906pt}{-2.1892pt}{2.1892pt}{-1.20906pt}{2.1892pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.7}{0.0}{0.0}{0.7}{-1.22499pt}{-1.57887pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$ [25]. Our algorithm
can be used to provide the synchronization for the first half of this
requirement, which is sufficient for instances with a connected shared graph.

(a)

(b)

Figure 8:  An instance of Connected SEFE $G=G^{\leavevmode\hbox to4.38pt{\vbox
to4.38pt{\pgfpicture\makeatletter\hbox{\hskip 2.18805pt\lower-2.18805pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{1.98805pt}{0.0pt}\pgfsys@curveto{1.98805pt}{1.09798pt}{1.09798pt}{1.98805pt}{0.0pt}{1.98805pt}\pgfsys@curveto{-1.09798pt}{1.98805pt}{-1.98805pt}{1.09798pt}{-1.98805pt}{0.0pt}\pgfsys@curveto{-1.98805pt}{-1.09798pt}{-1.09798pt}{-1.98805pt}{0.0pt}{-1.98805pt}\pgfsys@curveto{1.09798pt}{-1.98805pt}{1.98805pt}{-1.09798pt}{1.98805pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.7}{0.0}{0.0}{0.7}{-1.10248pt}{-1.42099pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}\cap
G^{\leavevmode\hbox to4.38pt{\vbox
to4.38pt{\pgfpicture\makeatletter\hbox{\hskip 2.18805pt\lower-2.18805pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{1.98805pt}{0.0pt}\pgfsys@curveto{1.98805pt}{1.09798pt}{1.09798pt}{1.98805pt}{0.0pt}{1.98805pt}\pgfsys@curveto{-1.09798pt}{1.98805pt}{-1.98805pt}{1.09798pt}{-1.98805pt}{0.0pt}\pgfsys@curveto{-1.98805pt}{-1.09798pt}{-1.09798pt}{-1.98805pt}{0.0pt}{-1.98805pt}\pgfsys@curveto{1.09798pt}{-1.98805pt}{1.98805pt}{-1.09798pt}{1.98805pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.7}{0.0}{0.0}{0.7}{-1.10248pt}{-1.42099pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$ (a) and the
equivalent Synchronized Planarity instance $I$ (b).

######  Theorem 16.

Connected SEFE can be solved in $O(n^{2})$ time.

###### Proof.

We add both $G^{\leavevmode\hbox to4.78pt{\vbox
to4.78pt{\pgfpicture\makeatletter\hbox{\hskip 2.38919pt\lower-2.38919pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.1892pt}{0.0pt}\pgfsys@curveto{2.1892pt}{1.20906pt}{1.20906pt}{2.1892pt}{0.0pt}{2.1892pt}\pgfsys@curveto{-1.20906pt}{2.1892pt}{-2.1892pt}{1.20906pt}{-2.1892pt}{0.0pt}\pgfsys@curveto{-2.1892pt}{-1.20906pt}{-1.20906pt}{-2.1892pt}{0.0pt}{-2.1892pt}\pgfsys@curveto{1.20906pt}{-2.1892pt}{2.1892pt}{-1.20906pt}{2.1892pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.7}{0.0}{0.0}{0.7}{-1.22499pt}{-1.57887pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$ and
$G^{\leavevmode\hbox to4.78pt{\vbox
to4.78pt{\pgfpicture\makeatletter\hbox{\hskip 2.38919pt\lower-2.38919pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.1892pt}{0.0pt}\pgfsys@curveto{2.1892pt}{1.20906pt}{1.20906pt}{2.1892pt}{0.0pt}{2.1892pt}\pgfsys@curveto{-1.20906pt}{2.1892pt}{-2.1892pt}{1.20906pt}{-2.1892pt}{0.0pt}\pgfsys@curveto{-2.1892pt}{-1.20906pt}{-1.20906pt}{-2.1892pt}{0.0pt}{-2.1892pt}\pgfsys@curveto{1.20906pt}{-2.1892pt}{2.1892pt}{-1.20906pt}{2.1892pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.7}{0.0}{0.0}{0.7}{-1.22499pt}{-1.57887pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$ to the Synchronized
Planarity instance and also add a bond $b^{\leavevmode\hbox to4.78pt{\vbox
to4.78pt{\pgfpicture\makeatletter\hbox{\hskip 2.38919pt\lower-2.38919pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.1892pt}{0.0pt}\pgfsys@curveto{2.1892pt}{1.20906pt}{1.20906pt}{2.1892pt}{0.0pt}{2.1892pt}\pgfsys@curveto{-1.20906pt}{2.1892pt}{-2.1892pt}{1.20906pt}{-2.1892pt}{0.0pt}\pgfsys@curveto{-2.1892pt}{-1.20906pt}{-1.20906pt}{-2.1892pt}{0.0pt}{-2.1892pt}\pgfsys@curveto{1.20906pt}{-2.1892pt}{2.1892pt}{-1.20906pt}{2.1892pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.7}{0.0}{0.0}{0.7}{-1.22499pt}{-1.57887pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}b^{\leavevmode\hbox
to4.78pt{\vbox to4.78pt{\pgfpicture\makeatletter\hbox{\hskip
2.38919pt\lower-2.38919pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.1892pt}{0.0pt}\pgfsys@curveto{2.1892pt}{1.20906pt}{1.20906pt}{2.1892pt}{0.0pt}{2.1892pt}\pgfsys@curveto{-1.20906pt}{2.1892pt}{-2.1892pt}{1.20906pt}{-2.1892pt}{0.0pt}\pgfsys@curveto{-2.1892pt}{-1.20906pt}{-1.20906pt}{-2.1892pt}{0.0pt}{-2.1892pt}\pgfsys@curveto{1.20906pt}{-2.1892pt}{2.1892pt}{-1.20906pt}{2.1892pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.7}{0.0}{0.0}{0.7}{-1.22499pt}{-1.57887pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$ for each vertex
$x\in G$. The parallel edges of the bond correspond to the edges incident to
$x$ in $G$. Again, we add further degree-1 vertices so that we can match
$x^{\leavevmode\hbox to4.78pt{\vbox
to4.78pt{\pgfpicture\makeatletter\hbox{\hskip 2.38919pt\lower-2.38919pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.1892pt}{0.0pt}\pgfsys@curveto{2.1892pt}{1.20906pt}{1.20906pt}{2.1892pt}{0.0pt}{2.1892pt}\pgfsys@curveto{-1.20906pt}{2.1892pt}{-2.1892pt}{1.20906pt}{-2.1892pt}{0.0pt}\pgfsys@curveto{-2.1892pt}{-1.20906pt}{-1.20906pt}{-2.1892pt}{0.0pt}{-2.1892pt}\pgfsys@curveto{1.20906pt}{-2.1892pt}{2.1892pt}{-1.20906pt}{2.1892pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.7}{0.0}{0.0}{0.7}{-1.22499pt}{-1.57887pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$ with
$b^{\leavevmode\hbox to4.78pt{\vbox
to4.78pt{\pgfpicture\makeatletter\hbox{\hskip 2.38919pt\lower-2.38919pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.1892pt}{0.0pt}\pgfsys@curveto{2.1892pt}{1.20906pt}{1.20906pt}{2.1892pt}{0.0pt}{2.1892pt}\pgfsys@curveto{-1.20906pt}{2.1892pt}{-2.1892pt}{1.20906pt}{-2.1892pt}{0.0pt}\pgfsys@curveto{-2.1892pt}{-1.20906pt}{-1.20906pt}{-2.1892pt}{0.0pt}{-2.1892pt}\pgfsys@curveto{1.20906pt}{-2.1892pt}{2.1892pt}{-1.20906pt}{2.1892pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.7}{0.0}{0.0}{0.7}{-1.22499pt}{-1.57887pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$ and
$x^{\leavevmode\hbox to4.78pt{\vbox
to4.78pt{\pgfpicture\makeatletter\hbox{\hskip 2.38919pt\lower-2.38919pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.1892pt}{0.0pt}\pgfsys@curveto{2.1892pt}{1.20906pt}{1.20906pt}{2.1892pt}{0.0pt}{2.1892pt}\pgfsys@curveto{-1.20906pt}{2.1892pt}{-2.1892pt}{1.20906pt}{-2.1892pt}{0.0pt}\pgfsys@curveto{-2.1892pt}{-1.20906pt}{-1.20906pt}{-2.1892pt}{0.0pt}{-2.1892pt}\pgfsys@curveto{1.20906pt}{-2.1892pt}{2.1892pt}{-1.20906pt}{2.1892pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.7}{0.0}{0.0}{0.7}{-1.22499pt}{-1.57887pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$ with
$b^{\leavevmode\hbox to4.78pt{\vbox
to4.78pt{\pgfpicture\makeatletter\hbox{\hskip 2.38919pt\lower-2.38919pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.1892pt}{0.0pt}\pgfsys@curveto{2.1892pt}{1.20906pt}{1.20906pt}{2.1892pt}{0.0pt}{2.1892pt}\pgfsys@curveto{-1.20906pt}{2.1892pt}{-2.1892pt}{1.20906pt}{-2.1892pt}{0.0pt}\pgfsys@curveto{-2.1892pt}{-1.20906pt}{-1.20906pt}{-2.1892pt}{0.0pt}{-2.1892pt}\pgfsys@curveto{1.20906pt}{-2.1892pt}{2.1892pt}{-1.20906pt}{2.1892pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.7}{0.0}{0.0}{0.7}{-1.22499pt}{-1.57887pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$; see Figure 8. The
Synchronized Planarity algorithm can then be used to obtain embeddings
$\mathcal{E}_{1}$ and $\mathcal{E}_{2}$ for $G^{\leavevmode\hbox
to4.78pt{\vbox to4.78pt{\pgfpicture\makeatletter\hbox{\hskip
2.38919pt\lower-2.38919pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.1892pt}{0.0pt}\pgfsys@curveto{2.1892pt}{1.20906pt}{1.20906pt}{2.1892pt}{0.0pt}{2.1892pt}\pgfsys@curveto{-1.20906pt}{2.1892pt}{-2.1892pt}{1.20906pt}{-2.1892pt}{0.0pt}\pgfsys@curveto{-2.1892pt}{-1.20906pt}{-1.20906pt}{-2.1892pt}{0.0pt}{-2.1892pt}\pgfsys@curveto{1.20906pt}{-2.1892pt}{2.1892pt}{-1.20906pt}{2.1892pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.7}{0.0}{0.0}{0.7}{-1.22499pt}{-1.57887pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$ and
$G^{\leavevmode\hbox to4.78pt{\vbox
to4.78pt{\pgfpicture\makeatletter\hbox{\hskip 2.38919pt\lower-2.38919pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.1892pt}{0.0pt}\pgfsys@curveto{2.1892pt}{1.20906pt}{1.20906pt}{2.1892pt}{0.0pt}{2.1892pt}\pgfsys@curveto{-1.20906pt}{2.1892pt}{-2.1892pt}{1.20906pt}{-2.1892pt}{0.0pt}\pgfsys@curveto{-2.1892pt}{-1.20906pt}{-1.20906pt}{-2.1892pt}{0.0pt}{-2.1892pt}\pgfsys@curveto{1.20906pt}{-2.1892pt}{2.1892pt}{-1.20906pt}{2.1892pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.7}{0.0}{0.0}{0.7}{-1.22499pt}{-1.57887pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$, respectively. As
pipes reverse the order of incident edges, a solution for the Synchronized
Planarity instance will have one of the two graphs mirrored with respect to
the graph shared with the other, i.e. the solution for the SEFE instance is
$\mathcal{E}_{1},\overline{\mathcal{E}_{2}}$. ∎

## References

  * [1] H. A. Akitaya, R. Fulek, and C. D. Tóth.  Recognizing weak embeddings of graphs.  ACM Transactions on Algorithms, 15(4):1–27, 2019.  doi:10.1145/3344549.
  * [2] P. Angelini and G. Da Lozzo.  SEFE = c-planarity?  The Computer Journal, 59(12):1831–1838, 2016.  doi:10.1093/comjnl/bxw035.
  * [3] P. Angelini and G. Da Lozzo.  Clustered planarity with pipes.  Algorithmica, 81(6):2484–2526, 2019.  doi:10.1007/s00453-018-00541-w.
  * [4] G. D. Battista and R. Tamassia.  On-line maintenance of triconnected components with SPQR-trees.  Algorithmica, 15(4):302–318, 1996.  doi:10.1007/bf01961541.
  * [5] F. Bernhart and P. C. Kainen.  The book thickness of a graph.  Journal of Combinatorial Theory, Series B, 27(3):320–331, 1979\.  doi:10.1016/0095-8956(79)90021-2.
  * [6] T. Bläsius, A. Karrer, and I. Rutter.  Simultaneous embedding: Edge orderings, relative positions, cutvertices.  Algorithmica, 80(4):1214–1277, 2017.  doi:10.1007/s00453-017-0301-9.
  * [7] T. Bläsius and I. Rutter.  Simultaneous PQ-ordering with applications to constrained embedding problems.  ACM Trans. Algorithms, 12(2):16:1–16:46, 2016.  doi:10.1145/2738054.
  * [8] T. Bläsius, S. G. Kobourov, and I. Rutter.  Simultaneous embedding of planar graphs.  In R. Tamassia, editor, Handbook of Graph Drawing and Visualization, chapter 11, pages 349–381. CRC Press, Taylor & Francis Group, 2013.  arXiv:1204.5853.
  * [9] T. Bläsius and I. Rutter.  A new perspective on clustered planarity as a combinatorial embedding problem.  Theoretical Computer Science, 609:306–315, 2016.  arXiv:1506.05673v1, doi:10.1016/j.tcs.2015.10.011.
  * [10] K. S. Booth and G. S. Lueker.  Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms.  Journal of Computer and System Sciences, 13(3):335–379, 1976.  doi:10.1016/s0022-0000(76)80045-1.
  * [11] J. Carmesin.  Embedding simply connected 2-complexes in 3-space – V. a refined Kuratowski-type characterisation.  2017\.  arXiv:1709.04659v3.
  * [12] P. F. Cortese, G. D. Battista, F. Frati, M. Patrignani, and M. Pizzonia.  C-planarity of c-connected clustered graphs.  Journal of Graph Algorithms and Applications, 12(2):225–262, 2008\.  doi:10.7155/jgaa.00165.
  * [13] P. F. Cortese and M. Patrignani.  Clustered planarity = flat clustered planarity.  In T. C. Biedl and A. Kerren, editors, Proceedings of the 26th International Symposium on Graph Drawing and Network Visualization (GD’18), volume 11282 of LNCS, pages 23–38. Springer, 2018.  doi:10.1007/978-3-030-04414-5_2.
  * [14] A. de Mesmay, Y. Rieck, E. Sedgwick, and M. Tancer.  Embeddability in $\mathbb{R}^{3}$ is NP-hard.  In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’18), pages 1316–1329, 2018.  doi:10.1137/1.9781611975031.86.
  * [15] R. Diestel.  Graph Theory.  Graduate Texts in Mathematics. Springer, 5th edition edition, 2017.  doi:10.1007/978-3-662-53622-3.
  * [16] Q.-W. Feng, R. F. Cohen, and P. Eades.  Planarity for clustered graphs.  In P. G. Spirakis, editor, Proceedings of the 3rd Annual European Symposium on Algorithms (ESA’95), volume 979 of LNCS, pages 213–226. Springer, 1995.  doi:10.1007/3-540-60313-1_145.
  * [17] R. Fulek, J. Kynčl, I. Malinović, and D. Pálvölgyi.  Clustered planarity testing revisited.  The Electronic Journal of Combinatorics, 22(4), 2015.  doi:10.37236/5002.
  * [18] R. Fulek and C. D. Tóth.  Atomic embeddability, clustered planarity, and thickenability.  In Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’20), pages 2876–2895. SIAM, 2020.  arXiv:1907.13086v1, doi:10.1137/1.9781611975994.175.
  * [19] C. Gutwenger, M. Jünger, S. Leipert, P. Mutzel, M. Percan, and R. Weiskircher.  Advances in c-planarity testing of clustered graphs.  In S. G. Kobourov and M. T. Goodrich, editors, Proceedings of the 10th International Symposium on Graph Drawing (GD’02), volume 2528 of LNCS, pages 220–235. Springer, 2002.  doi:10.1007/3-540-36151-0_21.
  * [20] C. Gutwenger, K. Klein, and P. Mutzel.  Planarity testing and optimal edge insertion with embedding constraints.  Journal of Graph Algorithms and Applications, 12(1):73–95, 2008\.  doi:10.7155/jgaa.00160.
  * [21] C. Gutwenger and P. Mutzel.  A linear time implementation of SPQR-trees.  In J. Marks, editor, Proceedings of the 8th International Symposium on Graph Drawing (GD’00), volume 1984 of LNCS, pages 77–90. Springer, 2000.  doi:10.1007/3-540-44541-2_8.
  * [22] F. Hadlock.  Finding a maximum cut of a planar graph in polynomial time.  SIAM J. Comput., 4(3):221–225, 1975.  doi:10.1137/0204019.
  * [23] J. E. Hopcroft and R. E. Tarjan.  Dividing a graph into triconnected components.  SIAM J. Comput., 2(3):135–158, 1973.  doi:10.1137/0202012.
  * [24] W.-L. Hsu.  PC-trees vs. PQ-trees.  In J. Wang, editor, Proceedings of the 7th Annual International Conference on Computing and Combinatorics (COCOON’01), volume 2108 of LNCS, pages 207–217. Springer, 2001.  doi:10.1007/3-540-44679-6_23.
  * [25] M. Jünger and M. Schulz.  Intersection graphs in simultaneous embedding with fixed edges.  Journal of Graph Algorithms and Applications, 13(2):205–218, 2009\.  doi:10.7155/jgaa.00184.
  * [26] T. Lengauer.  Hierarchical planarity testing algorithms.  Journal of the ACM, 36(3):474–509, 1989.  doi:10.1145/65950.65952.
  * [27] L. Neuwirth.  An algorithm for the construction of 3-manifolds from 2-complexes.  Mathematical Proceedings of the Cambridge Philosophical Society, 64(3):603–614, 1968.  doi:10.1017/S0305004100043279.
  * [28] M. Schaefer.  Toward a theory of planarity: Hanani-tutte and planarity variants.  Journal of Graph Algorithms and Applications, 17(4):367–440, 2013\.  doi:10.7155/jgaa.00298.
  * [29] W.-K. Shih and W.-L. Hsu.  A new planarity test.  Theoretical Computer Science, 223(1-2):179–191, 1999.  doi:10.1016/s0304-3975(98)00120-0.
  * [30] R. Tamassia, editor.  Handbook of Graph Drawing and Visualization.  CRC Press, Taylor & Francis Group, 2014.  doi:10.1201/b15385.