# Constrained Planarity in Practice

Engineering the Synchronized Planarity Algorithm

Simon D. Fink<EMAIL_ADDRESS>0000-0002-2754-1195 and  Ignaz Rutter
<EMAIL_ADDRESS>0000-0002-3794-4406 University of PassauFaculty of
Computer Science and MathematicsPassauGermany

(2018)

###### Abstract.

In the constrained planarity setting, we ask whether a graph admits a planar
drawing that additionally satisfies a given set of constraints. These
constraints are often derived from very natural problems; prominent examples
are Level Planarity, where vertices have to lie on given horizontal lines
indicating a hierarchy, and Clustered Planarity, where we additionally draw
the boundaries of clusters which recursively group the vertices in a crossing-
free manner. Despite receiving significant amount of attention and substantial
theoretical progress on these problems, only very few of the found solutions
have been put into practice and evaluated experimentally.
In this paper, we describe our implementation of the recent quadratic-time
algorithm by Bläsius et al. (bfr-spw-21, ) for solving the problem
Synchronized Planarity, which can be seen as a common generalization of
several constrained planarity problems, including the aforementioned ones. Our
experimental evaluation on an existing benchmark set shows that even our
baseline implementation outperforms all competitors by at least an order of
magnitude. We systematically investigate the degrees of freedom in the
implementation of the Synchronized Planarity algorithm for larger instances
and propose several modifications that further improve the performance.
Altogether, this allows us to solve instances with up to 100 vertices in
milliseconds and instances with up to $100\,000$ vertices within a few
minutes.

††copyright: acmcopyright††journalyear: 2018††doi: XXXXXXX.XXXXXXX††price:
15.00††isbn: 978-1-4503-XXXX-X/18/06

###### Acknowledgements.

Funded by the Deutsche Forschungsgemeinschaft (German Research Foundation,
DFG) under grant RU-1903/3-1.

##  1\. Introduction

In many practical graph drawing applications we not only seek any drawing that
maximizes legibility, but also want to encode additional information via
certain aspects of the underlying layout. Examples are _hierarchical_ drawings
like organizational charts, where we encode a hierarchy among vertices by
placing them on predefined levels, _clustered_ drawings, where we group
vertices by enclosing them in a common region, and _animated_ drawings, where
changes to a graph are shown in steps while keeping a static part fixed. In
practice, clustered drawings are for example UML diagrams, where classes are
grouped according to the package they are contained in, computer networks,
where devices are grouped according to their subnetwork, and integrated
circuits, where certain components should be placed close to each other. As
crossings negatively affect the readability of drawings (pac-gla-02, ; wpcm-
cmo-02, ), we preferably seek planar, i.e. crossing-free, drawings. The
combination of these concepts leads to the field of constrained planarity
problems, where we ask whether a graph admits a planar drawing that satisfies
a given set of constraints. This includes the problems Level Planarity (jlm-
lpt-98, ; brue-pvf-21, ), Clustered Planarity (br-anp-16, ; len-hpt-89, ; fce-
pfc-95, ), and Simultaneous Embedding with Fixed Edges (SEFE) (bcd-osp-07, ;
bkr-seo-13, ; rut-se-20, ), which respectively model the aforementioned
applications; see Figure 1. Formally, these problems are defined as follows.

Figure 1.  Examples of constrained planarity problems: Level Planarity (a),
Clustered Planarity (b), SEFE (c).

Problem Level Planarity Given:  graph $G$, leveling function
$\ell:V(G)\to\mathbb{N}$ Question:  Is there a planar drawing where each
vertex $v\in V(G)$ has y-coordinate $\ell(v)$ and all edges are drawn
y-monotone?

Problem Clustered Planarity Given:  graph $G$, rooted cluster tree $T$,
cluster assignment function $\gamma:V(G)\to V(T)$ Question:  Is there a planar
drawing where, for each cluster $c\in V(T)$, we can add a simple closed region
that (1):  encloses exactly the vertices mapped to $c$ or one of its
descendants in $T$, and (2):  has a border that crosses each edge that
connects a vertex within its interior to a vertex on its outside exactly once,
but no other edge or cluster region border?

Problem SEFE Given:  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}}},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}}}$ with a shared 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}}}$ Question:  Are
there a planar drawings of $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}}}$ that induce the
same drawing of their shared part $G$?

In the last years, the family formed by these problems and other variants of
constrained planarity received a lot of attention in the field of Graph
Drawing. Efficient algorithms were discovered for many of them, while a few
others turned out to be NP-complete; see (sch-tat-13, ) and (dloz-pgw-15, )
for an overview. In contrast to the extensive theoretical considerations and
the direct motivation by applications, only very few of the found algorithms
(many of which have a linear or at most quadratic asymptotic running time)
have been implemented and evaluated in practice. This also contrasts the wide
variety of implementations available for the different linear-time algorithms
for ordinary, i.e., unconstrained planarity (pat-pta-13, ), which have also
been thoroughly assessed in terms of their practical running time (fmr-tta-06,
; bcpb-smy-04, ).

The recently introduced problem Synchronized Planarity (bfr-spw-21, ) not only
generalizes many constrained planarity variants, among them in particular
Level and Clustered Planarity as well as variants of SEFE, but also has a
comparatively simple quadratic-time solution. Akin to the Goldberg and Tarjan
push-relabel algorithm (gt-ana-88, ), it uses few and simple operations that
can be applied in arbitrary order. Through reductions from many other problems
(see Figure 3 for an overview), an implementation would also allow to solve
other constrained planarity problems for which no practical solution is
available. This wide area of possible applications and the fact that the
algorithm offers several degrees of freedom make it an ideal starting point
for algorithm engineering.

In this paper, we describe our implementation of the Synchronized Planarity
algorithm, which we evaluate by comparing its results and running times to
those of two existing implementations for the Clustered Planarity problem. We
complement the previous theoretical running time analysis by Bläsius et al.
(bfr-spw-21, ) with practical measurements, highlighting which parts of the
algorithm take the most time. Based on this, we engineer the algorithm by
analyzing how to best employ the degrees of freedom present in the algorithm
and by proposing algorithmic improvements to overcome performance bottlenecks.
Section 2 provides more background on constrained planarity and Synchronized
Planarity in particular, while Section 3 gives an overview of previous
practical approaches to constrained planarity. In Section 4 we describe our
implementation of Synchronized Planarity and evaluate its performance in
comparison with the two other available Clustered Planarity implementations.
We tune the running time of our implementation to make it practical even on
large instances in Section 5. We analyze the effects of our engineering in
greater detail in Section 6.

Figure 2.  A planar graph (a), its SPQR-tree (b) and the corresponding
skeletons (c). Rigids are highlighted in red, parallels in green, and series
in blue. The embedding tree of the vertex marked in blue (d). Small black
disks are P-nodes, larger white disks are Q-nodes.

###  1.1. Preliminaries.

We rely on some well-known concepts from the fields of graph drawing and
planar graphs. We only briefly define the most important terms here and refer
to the theoretical description of the implemented algorithm (bfr-spw-21, ) for
more comprehensive definitions. A more gentle introduction to the concepts can
also be found in Chapter 1 of the Handbook of Graph Drawing and Visualization
(pat-pta-13, ). We consider two planar (i.e., crossing-free) drawings
equivalent if they define the same _rotation system_ , which specifies for
each vertex its _rotation_ , i.e., the cyclic order of the edges around the
vertex. An _embedding_ is an equivalence class of planar drawings induced by
this relation. An _embedding tree_ (bfr-spw-21, ) is a PQ-tree (bl-tft-76, )
that describes all possible rotations of a vertex in a planar graph; see
Figure 2d. Its leaves correspond to the incident edges, while its inner nodes
are either Q-nodes, which dictate a fixed ordering of their incident subtrees
that can only be reversed, or are P-nodes, which allow arbitrary permutation.
A BC-tree describes the decomposition of a connected graph into its
_biconnected_ components, which cannot be disconnected by the removal of a so-
called _cut-vertex_. Each node of a BC-tree represents either a cut-vertex or
a maximal biconnected _block_. We refer to a vertex that is not a cut-vertex
as _block-vertex_. An SPQR-tree (dbt-olm-96, ) describes the decomposition of
a biconnected graph into its _triconnected_ components, which cannot be
disconnected by the removal of a so-called _split-pair_ of two vertices. Each
inner node represents a _skeleton_ , which is either a triconnected _‘rigid’_
minor whose planar embedding can only be mirrored, a split-pair of two _pole_
vertices connected by multiple _‘parallel’_ subgraphs that can be permuted
arbitrarily, or a cycle formed by split-pairs separating a _‘series’_ of
subgraphs; see Figure 2c. All three kinds of trees can be computed in time
linear in the size of the given graph (br-spo-16, ; pat-pta-13, ; gm-alt-01,
).

##  2\. Constrained Planarity

Schaefer (sch-tat-13, , Figure 2) introduced a hierarchy on the various
variants of constrained planarity that have been studied in the past. Figure 3
shows a subset of this hierarchy, incorporating updates up to 2015 by Da Lozzo
(dloz-pgw-15, , Figure 0.1). Arrows indicate that the target problem either
generalizes the source problem or solves it via a reduction. In the version of
Da Lozzo, the problems Strip, Clustered and Synchronized Planarity as well as
(Connected) SEFE still formed a frontier of problems with unknown complexity,
separating efficiently solvable problems from those that are NP-hard. Since
then many of these problems were settled in P, especially due to the Clustered
Planarity solution from 2019 by Fulek and Tóth (ft-aec-22, ). The only problem
from this hierarchy that remains with an unknown complexity is SEFE. In this
section, we want to give a short summary of the history of Clustered Planarity
and SEFE, which we see central to the field of constrained planarity and which
also serve as a motivation for Synchronized Planarity. Afterwards, we will
give a short summary of the algorithm we implement for solving the latter
problem. We point the interested reader to the original description (bfr-
spw-21, ) for full details.

Figure 3. Constrained planarity variants related to Synchronized Planarity,
updated selection from (dloz-pgw-15, ). Problems and reductions marked in blue
are used for generating test instances.

Recall that in SEFE, we are given two graphs that share some common part and
we want to embed both graphs individually such that their common parts are
embedded the same way (bcd-osp-07, ; bkr-seo-13, ; rut-se-20, ). More general
SEFE variants are often NP-complete, e.g., the case with three given graphs
(gjp-sge-06, ), even if all share the same common part (aln-aos-15, ; sch-
tat-13, ). In contrast, more restricted variants are often efficiently
solvable, e.g., when the shared graph is biconnected, a star, a set of cycles,
or has a fixed embedding (abf-tts-12, ; br-dar-15, ; abf-tpo-15, ). The case
where the shared graph is connected, which is called Connected SEFE, was shown
to be equivalent to the so-called Partitioned $\mathcal{T}$-coherent 2-page
Book Embedding problem (abf-tts-12, ) and to be reducable to Clustered
Planarity (al-sc-16, ), all of which were recently shown to be efficiently
solvable (ft-aec-22, ). In contrast to these results, the complexity of the
general SEFE problem with two graphs sharing an arbitrary common graph is
still unknown.

Recall that in Clustered Planarity, the embedding has to respect a laminar
family of clusters, that is every vertex is assigned to some (hierarchically
nested) cluster and an edge may only cross a the border of a cluster’s region
if it connects a vertex from the inside with one from the outside (br-anp-16,
; len-hpt-89, ); see Figure 4 for an example. Lengauer (len-hpt-89, ) studied
and solved this problem as early as 1989 in the setting where the clusters are
connected. Feng et al. (fce-pfc-95, ), who coined the term Clustered
Planarity, rediscovered this algorithm and asked the general question where
disconnected clusters are allowed. This question remained open for 25 years.
In that time, polynomial-time algorithms were found for many special-cases
(adl-cpw-19, ; cdbf-cpo-08, ; fkmp-cpt-15, ; gjl-aic-02, ) before Fulek and
Tóth (ft-aec-22, ) found an $O((n+d)^{8})$ solution in 2019, where $d$ is the
number of crossings between a cluster-border and an edge leaving the cluster.
Shortly thereafter, Bläsius et al. (bfr-spw-21, ) gave a solution with running
time in $O((n+d)^{2})$ that works via a linear-time reduction to Synchronized
Planarity.

Figure 4. A Clustered Planarity instance (a), its cluster tree (b), and its
CD-tree representation (c).

In Synchronized Planarity, we are given a graph together with a set of _pipes_
, each of which pairs up two distinct vertices of the graph. Each pipe
synchronizes the rotation of its two paired-up vertices (its _endpoints_) in
the following sense: We seek a planar embedding of the graph where for each
pipe $\rho$, the rotations of its endpoints line up under the bijection
$\varphi_{\rho}$ associated with $\rho$ (bfr-spw-21, ). Formally, this problem
is defined as follows.

Problem Synchronized Planarity 111Note that we disregard the originally
included Q-vertices here, as they can also be modeled using pipes (bfr-spw-21,
, Section 5). Given:  graph $G$ and a set $\mathcal{P}$, where each _pipe_
$\rho\in\mathcal{P}$ consists of two distinct vertices $v_{1},v_{2}\in V(G)$
and a bijection $\varphi_{\rho}$ between the edges incident to $v_{1}$ and
those incident to $v_{2}$, and each vertex is part of at most one pipe
Question:  Is there a drawing of $G$ where for each pipe
$\rho=(v_{1},v_{2},\varphi_{\rho})$, the cyclic order of edges incident to
$v_{1}$ lines up with the order of edges incident to $v_{2}$ under the
bijection $\varphi_{\rho}$?

The motivation for this “synchronization” can best be seen by considering the
reduction from Clustered to Synchronized Planarity. At each cluster boundary,
we split the graph into two halves: one where we contract the inside of the
cluster into a single vertex and one where we contract the outside into a
single vertex. In a clustered planar embedding, the order of the edges
“leaving” one cluster (i.e. the rotation of its contracted vertex in the one
half) needs to match the order in which they “enter” the parent cluster (i.e.
the the rotation of the corresponding contracted vertex in the other half).
The graph resulting from separately contracting each side of a cluster
boundary is called CD-tree (br-anp-16, ); see Figure 4 and (bfr-spw-21, ,
Figure 6) for an example. Using this graph, the synchronization of rotations
can easily be modeled via Synchronized Planarity by pairing the two contracted
vertices corresponding to the same cluster boundary with a pipe.

Figure 5.  The operations for solving Synchronized Planarity (bfr-spw-21, ).
Pipes are indicated by orange dashed lines, their endpoints are shown as
larger disks. Top: Two cut-vertices paired-up by a pipe (left), the result of
encapsulating their incident blocks (middle) and the bipartite graph resulting
from joining both cut-vertices (right). Middle: A block-vertex pipe endpoint
(left) that has a non-trivial embedding tree (middle) that is propagated to
replace both the vertex and its partner (right). Bottom: Three different cases
of paired-up vertices with trivial embedding trees (blue) and how their pipes
can be removed or replaced (red).

In the quadratic algorithm for solving Synchronized Planarity, a pipe is
_feasible_ if one of the three following operation can be applied to remove
it.

EncapsulateAndJoin:

If both endpoints of the pipe are cut-vertices, they are “encapsulated” by
collapsing each incident block to a single vertex to obtain two stars with
paired-up centers. Additionally, we split the original components at the two
cut-vertices, so that each of their incident blocks is retained as separate
component with its own copy of the cut-vertex. These copies are synchronized
with the respective vertex incident to the original cut-vertex representing
the collapsed block. Now the cut-vertices can be removed by “joining” both
stars at their centers, i.e, by identifying their incident edges according to
the given bijection; see the top row of Figure 5.

PropagatePQ:

If one endpoint of the pipe is a block-vertex and has an embedding tree that
not only consists of a single P-node (i.e., it is _non-trivial_), a copy of
this embedding tree is inserted (“propagated”) in place of each respective
pipe endpoint. The inner nodes of the embedding trees are synchronized by
pairing corresponding vertices with a pipe; see the middle row of Figure 5.
Note that, as Q-nodes only have a binary embedding decision, they can more
easily be synchronized via a 2-SAT formula instead of using pipes.

SimplifyMatching:

In the remaining case, at least one of the endpoints of the pipe is a block-
vertex but has a trivial embedding tree. If the vertex (or, more precisely,
the parallel in the SPQR-tree that completely defines its rotation) can
respect arbitrary rotations, we can simply remove the pipe. When the other
pole of the parallel is also paired-up and has a trivial embedding tree, we
“short-circuit” the pipe across the parallel; see the bottom row of Figure 5.
One exception is if the pipe matches the poles of the same parallel, where we
can again remove the pipe without replacement.

The algorithm then works by simply applying a suitable operation on an
_arbitrary_ feasible pipe each step. Moreover, it can be shown that if a pipe
is not feasible, then this is directly caused by a close-by pipe with
endpoints of higher degree (bfr-spw-21, ). Especially, this means that
maximum-degree pipes are always feasible.

Each of the three operations runs in time linear in the degree of the removed
pipe once the embedding trees it depends on has been computed. This is
dominated by the time spent on computing the embedding tree, which is linear
in the size of the considered biconnected component. Every applied operation
removes a pipe, but potentially introduces new pipes of smaller degree.
Bläsius et al. (bfr-spw-21, ) show that the progress made by the removal of a
pipe always dominates the overhead of the newly-introduced pipes and that the
number of operations needed to remove all pipes is limited by the total degree
of all paired-up vertices. Furthermore, the resulting instance without pipes
can be solved and embedded in linear time. An embedding of the input graph can
then be obtained by undoing all changes made to the graph in reverse order
while maintaining the found embedding. The algorithm thus runs in the
following three simple phases:

  1. (1)

While pipes are left, choose and remove an arbitrary feasible pipe by applying
an operation.

  2. (2)

Solve and embed the resulting pipe-free (_reduced_) instance.

  3. (3)

Undo all applied operations while maintaining the embedding.

##  3\. Related Work

Surprisingly, in contrast to their intense theoretical consideration,
constrained planarity problems have only received little practical attention
so far. Of all variants, practical approaches to Clustered Planarity were
studied the most, although all implementations predate the first fully-correct
polynomial-time solution and thus either have an exponential worst-case
running time or cannot solve all instances. Chimani et al. (cgj-cmc-08, )
studied the problem of finding maximal cluster planar subgraphs in practice
using an Integer Linear Program (ILP) together with a branch-and-cut
algorithm. A later work (ck-sts-12, ) strengthened the ILP for the special
case of testing Clustered Planarity, further improving the practical running
time. The work by Gutwenger et al. (gms-pew-14, ) takes a different approach
by using a Hanani-Tutte-style formulation of the problem based on the work by
Schaefer (sch-tat-13, ). Unfortunately, their polynomial-time testing
algorithm cannot solve all instances and declines to make a decision for some
instances. The Hanani-Tutte-approach solved instances with up to 60 vertices
and 8 clusters in up to half a minute, while the ILP approach only solves
roughly 90 of these instances within 10 minutes (gms-pew-14, ).

The only other constrained planarity variant for which we could find
experimental results is Partitioned 2-page Book Embedding. Angelini et al.
(abb-iap-12, ) describe an implementation of the SPQR-tree-based linear-time
algorithm by Hong and Nagamochi (hn-tpb-09, ), which solves instances with up
to $100\,000$ vertices and two clusters in up to 40 seconds. Unfortunately,
their implementation is not publicly available. For (Radial) Level Planarity,
prototypical implementations were described in the dissertations by Leipert
(lei-lpt-98, ) and Bachmaier (bac-cpo-04, ), although in both cases neither
further information, experimental results, nor source code is available. The
lack of an accessible and correct linear-time implementation may be due to the
high complexity of the linear-time algorithms (brue-pvf-21, ). Simpler
algorithms with a super-linear running time have been proposed (hh-plp-07, ;
rsb-asf-01, ; fpss-hmd-12, ). For these, we could only find an implementation
by Estrella-Balderrama et al. (efk-gat-10, ) for the quadratic algorithm by
Harrigan and Healy (hh-plp-07, ). Unfortunately, this implementation has not
been evaluated experimentally and we were also unable to make it usable
independently of its Microsoft Foundation Classes GUI, with which it is
tightly intertwined.

We are not aware of further practical approaches for constrained planarity
variants. Note that while the problems Partitioned 2-page Book Embedding and
Level Planarity have linear-time solutions, they are much more restricted than
Synchronized Planarity (see Figure 3) and have no usable implementations
available. We thus focus our comparison on solutions to the Clustered
Planarity problem which, besides being a common generalization of both other
problems, fortunately also has all relevant implementations available.

Dataset | # | Vertices | Density | Components | Clusters/Pipes | $d$
---|---|---|---|---|---|---
C-OLD | $1643$ |  $\leq$$59$ | ($17.2$) |  $0.92.2$ (1.4) |  $=1$ |  | $\leq 19$ | ($4.2$) | $\leq 256$ | ($34.0$)
C-NCP | $13\,834$ |  $\leq$$500$ | ($236.8$) |  $0.62.9$ (1.9) | $\leq 48$ | ($21.7$) | $\leq 50$ | ($16.8$) | $\leq 5390$ | ($783.3$)
C-MED | $5171$ |  $\leq$$10^{3}$ | ($311.6$) |  $0.92.9$ (2.3) | $\leq 10$ | ($5.1$) | $\leq 53$ | ($16.1$) | $\leq 7221$ | ($831.8$)
C-LRG | $5096$ |  $\leq$$10^{5}$ | ($15\,214.1$) |  $0.53.0$ (2.4) | $\leq 100$ | ($29.8$) | $\leq 989$ | ($98.8$) | $\leq 2\,380\,013$ | ($44\,788.7$)
SEFE-LRG | $1008$ |  $\leq$$10^{4}$ | ($3800.0$) |  $1.12.4$ (1.7) |  $=1$ |  | $\leq 20\,000$ | ($7600.0$) | $\leq 113\,608$ | ($34\,762.4$)
SP-LRG | $1587$ |  $\leq$$10^{5}$ | ($25\,496.6$) |  $1.32.5$ (2.0) | $\leq 100$ | ($34.5$) | $\leq 20\,000$ | ($1467.4$) | $\leq 139\,883$ | ($9627.5$)

Table 1. Statistics for our different datasets, values in parentheses are
averages. Column # shows the number of instances while column $d$ shows the
total number of cluster-border edge crossings or the total degree of all
pipes, depending on the underlying instances.

##  4\. Clustered Planarity in Practice

In this section, we shortly describe our C++ implementation of the
Synchronized Planarity algorithm by Bläsius et al. (bfr-spw-21, ) and compare
its running time and results on instances derived from Clustered Planarity
with those of the two existing implementations by Chimani et al. (cgj-cmc-08,
; ck-sts-12, ) and by Gutwenger et al. (gms-pew-14, ). We base our
implementation on the graph data structures provided by the OGDF (cgj-tog-13,
) and, as the only other dependency, use the PC-tree implementation by Fink et
al. (fpr-eco-21, ) for the embedding trees. The PC-tree is a datastructure
that is conceptually equivalent to the PQ-tree we use as embedding tree, but
is faster in practice (fpr-eco-21, ).

The algorithm for Synchronized Planarity makes no restriction on how the next
feasible pipe should be chosen. For now, we will use a heap to always use a
pipe of maximum degree, as this ensures that the pipe is feasible. The
operations used for solving Synchronized Planarity heavily rely on
(bi-)connectivity information while also making changes to the graph that may
affect this information. As recomputing the information before each step would
pose a high overhead, we maintain this information in the form of a BC-forest
(i.e. a collection of BC-trees). To generate the embedding trees needed by the
PropagatePQ and SimplifyMatching operations, we implement the Booth-Lueker
algorithm for testing planarity (bl-tft-76, ; pat-pta-13, ) using PC-trees. We
use that, after processing all vertices of a biconnected component, the
resulting PC-tree corresponds to the embedding tree of the vertex that was
processed last.

###  4.1. Evaluation Set-Up.

We compare our implementation of Synchronized Planarity with the Clustered
Planarity implementations ILP by Chimani et al. (cgj-cmc-08, ; ck-sts-12, )
and HT by Gutwenger at al. (gms-pew-14, ). Both are written in C++ and are
part of the OGDF. The ILP implementation by Chimani et al. (cgj-cmc-08, ; ck-
sts-12, ) uses the ABACUS ILP solver (ABACUS, ) provided with the OGDF. We
refer to our Synchronized Planarity implementation processing pipes in
descending order of their degree as SP[d]. We use the embedding it generates
for yes-instances as certificate to validate all positive answers. For the
Hanani-Tutte algorithm, we give the running times for the modes with embedding
generation and verification (HT) and the one without (HT-f) separately. Note
that HT-f only checks an important necessary, but not sufficient condition and
thus may falsely classify negative instances as positive, see (gms-pew-14, ,
Figure 3) and (fkmp-cpt-15, , Figure 16) for examples where this is the case.
Variant HT tries to verify a positive answer by generating an embedding, which
works by incrementally fixing parts of a partial embedding and subsequently
re-running the test. This process may fail at any point, in which case the
algorithm can make no statement about whether the instance is positive or
negative (gms-pew-14, , Section 3.3). We note that, in any of our datasets, we
neither found a case of HT-f yielding a false-positive result nor a case of a
HT verification failing. The asymptotic running time of HT-f is bounded by
$O(n^{6})$ and the additional verification of HT adds a further factor of $n$
(gms-pew-14, ).

We combine the Clustered Planarity datasets that were previously used for
evaluations on HT and ILP to form the set C-OLD (cgj-cmc-08, ; ck-sts-12, ;
gms-pew-14, ). We apply the preprocessing rules of Gutwenger at al. (gms-
pew-14, ) to all instances and discard instances that become trivial, non-
planar or cluster-connected, since the latter are easy to solve (cdbf-cpo-08,
). This leaves $1643$ instances; see Table 1. To create the larger dataset
C-NCP, we used existing methods from the OGDF to generate instances with up to
500 vertices and up to 50 clusters. This yields $15\,750$ instances, $13\,834$
out of which are non-trivial after preprocessing. As this dataset turned out
to contain only 10 yes-instances, we implemented a new clustered-planar
instance generator that is guaranteed to yield yes-instances. We use it on
random planar graphs with up to $1000$ vertices to generate $6300$ clustered-
planar instances with up to 50 clusters. Out of these, $5171$ are non-trivial
after preprocessing and make up our dataset C-MED. We provide full details on
the generation of our dataset at the end of this section.

We run our experiments on Intel Xeon E5-2690v2 CPUs (3.00 GHz, 10 Cores, 25 MB
Cache) with a memory usage limit of 6 GB. As all implementations are single-
threaded, we run multiple experiments in parallel using one core per
experiment. This allows us to test more instances while causing a small
overhead which affects all implementations in the same way. The machines run
Debian 11 with a 5.10 Linux Kernel. All binaries are compiled statically using
gcc 10.2.1 with flags -O3 -march=native and link-time optimization enabled. We
link against slightly modified versions of OGDF 2022.02 and the PC-tree
implementation by Fink et al. (fpr-eco-21, ). The source code of our
implementation and all modifications are available at
github.com/N-Coder/syncplan, 222It is also archived at Software Heritage with
ID swh:1:snp:0dae4960cc1303cc3575cf04924e19d664f8ad87. while our dataset is on
Zenodo with DOI 10.5281/zenodo.7896021.

(a)

(b)

Figure 6.  (a) Converting the subtree $\\{a,b,c,d\\}$ with root $a$ (shown in
orange) into a cluster will separate vertices $u$ and $v$, as the edge $bd$
(dashed) will also be part of the cluster. (b) A clustered-planar graph with
two clusters (in addition to the root cluster) that HT classifies as
“nonCPlanarVerified”.

#### Details on Dataset Generation

The dataset C-OLD is comprised of the datasets P-Small, P-Medium, P-Large by
Chimani and Klein (ck-sts-12, ) together with PlanarSmallR (a version of
PlanarSmall (cgj-cmc-08, ) with preprocessing applied), PlanarMediumR and
PlanarLargeR by Gutwenger et al. (gms-pew-14, ). The preprocessing reduced the
dataset of Chimani and Klein (ck-sts-12, ) to 64 non-trivial instances,
leading to dataset C-OLD containing $1643$ instances in total.

The OGDF library can generate an entirely random clustering by selecting
random subsets of vertices. It can also generate a random clustered-planar and
cluster-connected clustering on a given graph by running a depth-first search
that is stopped at random vertices, forming new clusters out of the discovered
trees. To generate non-cluster-connected but clustered-planar instances, we
temporarily add the edges necessary to make a disconnected input graph
connected. For the underlying graphs of C-NCP, we use the OGDF to generate
three instances for each combination of $n\in\\{100,200,300,400,500\\}$ nodes,
$m\in\\{n,1.5n,2n,2.5n,3n-6\\}$ edges, and $d\in\\{10,20,30,40,50\\}$ distinct
connected components. For each input graph, we generate six different
clusterings, three entirely random and three random clustered-planar, with
$c\in\\{3,5,10,20,30,40,50\\}$ clusters. This yields $15\,750$ instances,
$13\,834$ out of which are non-trivial after preprocessing.

It turns out that roughly 90 of these instances are not clustered-planar (see
Table 2), even though half of them are generated by a method claiming to only
generate clustered-planar instances. This is because the random DFS-subtree
used for clusters by the OGDF only ensures that the generated cluster itself,
but not its complement are connected. Thus, if the subgraph induced by the
selected vertices contains a cycle, this cycle may separate the outside of the
cluster; see Figure 6(a). To reliably generate yes-instances, we implemented a
third method for generating random clusterings. We first add temporary edges
to connect and triangulate the given input graph. Afterwards, we also generate
a random subtree and contract it into a cluster. Each visited vertex is added
to the tree with a probability set according to the desired number of vertices
per cluster. To ensure the non-tree vertices remain connected, we only add
vertices to the tree whose contraction leaves the graph triangulated, i.e.,
that have at most two neighbors that are already selected for the tree. We
convert the selected random subtrees into clusters and contract them for the
next iterations until all vertices have been added to a cluster.

As we do not need multiple connected components to ensure the instance is not
cluster-connected for our Clustered Planarity instance generator, we used
fewer steps for the corresponding parameter, but extended the number of nodes
up to $1000$ for C-MED. The underlying graphs are thus comprised of three
instances for each combination of $1\leq n\leq 1000$ nodes with $0\equiv n\mod
100$ (i.e. $n$ is a multiple of 100), $m\in\\{n,1.5n,2n,2.5n,3n-6\\}$ edges,
and $d\in\\{1,10,25,50\\}$ distinct connected components. For each input
graph, we generate three random clustered-planar clusterings with an expected
number of $c\in\\{3,5,10,20,30,40,50\\}$ clusters. This yields 6300 instances
which are guaranteed to be clustered-planar, $5171$ out of which are non-
trivial after preprocessing and make up our dataset C-MED.

| C-OLD | C-NCP | C-MED
---|---|---|---
| ILP | HT | HT-f | SP[d] | ILP | HT | HT-f | SP[d] | ILP | HT | HT-f | SP[d]
Y | $732$ | $792$ | $792$ | $792$ | $181$ | $1327$ | $1534$ | $1535$ | $953$ | $762$ | $2696$ | $5170$
N | $800$ | $851$ | $851$ | $851$ | $946$ | $6465$ | $6463$ | $12\,308$ | $0$ | $85$ | $85$ | $0$
ERR | $0$ | $0$ | $0$ | $0$ | $5214$ | $0$ | $0$ | $0$ | $1263$ | $0$ | $0$ | $0$
TO | $111$ | $0$ | $0$ | $0$ | $7502$ | $6051$ | $5846$ | $0$ | $2955$ | $4324$ | $2390$ | $1$

Table 2. Counts of the results ‘yes’, ‘no’, ‘error’, and ‘timed out’ on C-OLD,
C-NCP and C-MED.

(a)

(b)

Figure 7.  Median running times on dataset C-OLD (a) together with the
underlying scatter plot (b). For each algorithm, we show running times for
yes- and no-instances separately. Markers show medians of bins each containing
10 of the instances. Shaded regions around each line show inter-quartile
ranges.

###  4.2. Results.

Table 2 shows the results of running the different algorithms. The dataset
C-OLD is split in roughly equal halves between yes- and no-instances and all
algorithms yield the same results, except for the 111 instances for which the
ILP ran into our 5-minute timeout. The narrow inter-quartile ranges in Figure
7 show that the running time for HT and SP[d] clearly depends on the number of
crossings between cluster boundaries and edges in the given instance, while it
is much more scattered for ILP. Still, all instances with less than 20 such
crossings could be solved by ILP. For HT, we can see that the verification and
embedding of yes-instances has an overhead of at least an order of magnitude
over the non-verifying HT-f. The running times for HT on no-instances as well
as the times for HT-f on any type of instance are the same, showing that the
overhead is solely caused by the verification while the base running time is
always the same. For the larger instances in this test set, SP[d] is an order
of magnitude faster than HT-f. For SP[d], we also see a division between yes-
and no-instances, where the latter can be solved faster, but also with more
scattered running times. This is probably due to the fact that the test can
fail at any (potentially very early) reduction step or when solving the
reduced instance. Furthermore, we additionally generate an embedding for
positive instances, which may cause the gap between yes- and no-instances.

(a)

(b)

Figure 8.  Median running times (a) and scatter plot (b) on dataset C-NCP.

The running times on dataset C-NCP are shown in Figure 8. The result counts in
Table 2 show that only a small fraction of the instances are positive. With
only up to $300$ cluster-edge crossings these instances are also comparatively
small. The growth of the running times is similar to the one already observed
for the smaller instances in Figure 7. HT-f now runs into the timeout for
almost all yes-instances of size $200$ or larger, and both HT and HT-f time
out for all instances of size $1500$ and larger. The ILP only manages to solve
very few of the instances, often reporting an “undefined optimization result
for c-planarity computation” as error; see Table 2. The algorithms all agree
on the result if they do not run into a timeout or abort with an error, except
for one instance that HT classifies as negative while SP[d] found a (positive)
solution and also verified its correctness using the generated embedding as
certificate. This is even though the Hanani-Tutte approach by Gutwenger et al.
(gms-pew-14, ) should answer “no” only if the instance truly is negative.
Figure 6(b) shows a minimal minor of the instance for which the results still
disagree.

The running times on dataset C-MED with only positive instances shown in
Figure 9 are in accordance with the previous results. We now also see more
false-negative answers from the HT approach, which points to an error in its
implementation; see also Table 2. The plots clearly show that our approach is
much faster than all others. As the Synchronized Planarity reduction fails at
an arbitrary step for negative instances, the running times of positive
instances form an upper bound for those of negative instances. As we also see
verifying positive instances to obtain an embedding as far more common use-
case, we focus our following engineering on this case.

(a)

(b)

Figure 9.  Median running times (a) and scatter plot (b) on dataset C-MED.

##  5\. Engineering Synchronized Planarity

In this section, we study how degrees of freedom in the Synchronized Planarity
algorithm can be used to improve the running times on yes-instances. The
algorithm makes little restriction on the order in which pipes are processed,
which gives great freedom to the implementation for choosing the pipe it
should process next. In Sections 5.1 and 5.1 we investigate the effects of
deliberately choosing the next pipe depending on its degree and whether
removing it requires generation of an embedding tree. As mentioned by the
original description of the Synchronized Planarity algorithm, there are two
further degrees of freedom in the algorithm, both concerning pipes where both
endpoints are block-vertices. The first one is that if both endpoints
additionally lie in different connected components, we may apply either
PropagatePQ or (EncapsulateAnd)Join to remove the pipe. Joining the pipe
directly removes it entirely instead of splitting it into multiple smaller
ones, although at the cost of generating larger connected components. The
second one is for which endpoint of the pipe to compute an embedding tree when
applying PropagatePQ. Instead of computing only one embedding tree, we may
also compute both at once and then use their intersection. This preempts
multiple following operations propagating back embedding information
individually for each newly-created smaller pipe. We investigate the effect of
these two decisions in Sections 5.2 and 5.2. Lastly, we investigate an
alternative method for computing embedding trees in Section 5.3, where we
employ a more time-consuming algorithm that in return yields embedding trees
for all vertices of a biconnected component simultaneously instead of just for
a single vertex.

Figure 10.  Average time spent on different operations for SP[d] on C-MED.

To gain an initial overview over which parts could benefit the most from
improvements, Figure 10 shows how the running time is distributed across
different operations, averaged over all instances in C-MED. It shows that with
more than 20ms, that is roughly 40 of the overall running time, a large
fraction of time is spent on generating embedding trees, while the actual
operations contribute only a minor part of roughly 18 of the overall running
time. 27 of time is spent on solving and embedding the reduced instance and 15
is spent on undoing changes to obtain an embedding for the input graph. Thus,
the biggest gains can probably be made by reducing the time spent on
generating embedding information in the form of embedding trees. We use this
as rough guideline in our engineering process.

(a)

(b)

Figure 11.  C-LRG median absolute running times (a) and fraction of timeouts
(b). Each marker again corresponds to a bin containing 10 of the instances.
Figure 12.  Scatterplot and estimate for SP[d] running time growth behavior on
C-LRG.

#### Dataset Generation

To tune the running time of our algorithm on larger instances, we increased
the size of the generated instances by a factor of 100 by changing the
parameters of our own cluster-planar instance generator to $n\in\\{$$100$,
$500$, $1000$, $5000$, $10\,000$, $50\,000$, $100\,000$$\\},$
$d\in\\{1,10,100\\},$ $c\in\\{3,5,10,25,50,100,$1000$\\}$ for dataset C-LRG.
This yields 6615 instances, out of which $5096$ are non-trivial after
preprocessing; see Table 1.

In addition to the Clustered Planarity dataset we also generate a dataset that
uses the reduction from Connected SEFE. We do so by generating a random
connected and planar embedded graph as shared graph. Each exclusive graph
contains further edges which are obtained by randomly splitting the faces of
the embedded shared graph until we reach a desired density. For the shared
graphs, we generate three instances for each combination of $n\in\\{$$100$,
$500$, $1000$, $2500$, $5000$, $7500$, $10\,000$$\\}$ nodes and
$m\in\\{n,1.5n,2n,2.5n\\}$ edges. For $d\in\\{0.25,0.5,0.75,1\\}$, we then add
$(3n-6-m)\cdot d$ edges to each exclusive graph, i.e., the fraction $d$ of the
number of edges that can be added until the graph is maximal planar. We also
repeat this process three times with different initial random states for each
pair of shared graph and parameter $d$. This leads to the dataset SEFE-LRG
containing $1008$ instances.

We also generate a dataset of Synchronized Planarity instances by taking a
random planar embedded graph and adding pipes between vertices of the same
degree, using a bijection that matches their current rotation. The underlying
graphs are comprised of three instances for each combination of
$n\in\\{$$100$, $500$, $1000$, $5000$, $10\,000$, $50\,000$, $100\,000$$\\}$
nodes, $m\in\\{1.5n,2n,2.5n\\}$ edges, and $d\in\\{1,10,100\\}$ distinct
connected components. Note that we do not include graphs that would have no
edges, e.g., those with $n=100$ and $d=100$. For each input graph, we generate
three random Synchronized Planarity instances with $p\in\\{0.05n,0.1n,0.2n\\}$
pipes. This leads to the dataset SP-LRG containing $1587$ instances.

Altogether, our six datasets contain $28\,339$ instances in total. For the
test runs on these large instances, we increase the timeout to 1 hour.

Figure 11(a) shows the result of running our baseline variant SP[d] of the
Synchronized Planarity algorithm (together with selected further variants of
the algorithm from subsequent sections) on dataset C-LRG. Note that, because
the dataset spans a wide range of instance sizes and thus the running times
also span a range of different magnitudes, the plot uses a log scale for both
axes. Figure 11(b) shows the fraction of runs that timed out for each variant.
To estimate the practical runtime growth behavior, we also fit a polynomial to
the data shown in Figure 12 and thereby find the running time growth behavior
to be similar to $d^{1.5}$, where $d$ is the number of crossings between edges
and cluster borders.

(a)

(b)

Figure 13.  Relative running times when (a) sorting by pipe degree or
applicable operation and (b) when handling pipes between block-vertices via
intersection or join. Note the different scales on the y-axis.

###  5.1. Pipe Ordering

To be able to deliberately choose the next pipe, we keep a heap of all pipes
in the current instance, where the ordering function can be configured. Note
that the topmost pipe from this heap may not be feasible, in which case we
will give priority to the close-by pipe of higher degree that blocks the
current pipe from being feasible (see (bfr-spw-21, , Lemma 3.5)). We compare
the baseline variant SP[d] sorting by descending (i.e. largest first) degree
with the variant SP[a] sorting by ascending degree, and SP[r] using a random
order. Note that for these variants, the ordering does not depend on which
operation is applicable to a pipe or whether this operation requires the
generation of an embedding tree. To see whether making this distinction
affects the running time, we also compare the variants SP[d+c], which prefers
to process pipes on which EncapsulateAndJoin can be applied, and SP[d-c],
which defers such pipes to the very end, processing pipes requiring the
generation of embedding trees first.

To make the variants easier to compare, Figure 13(a) shows running times
relative to that of the baseline SP[d]. Note that we do not show the median of
the last bin, in which up to 70 of the runs timed out, while this number is
far lower for all previous bins; see Figure 11(b). Figure 13(a) shows that the
median running times differ by less than 10 between these variants. The
running time of SP[r] seems to randomly alternate between being slightly
slower and slightly faster than SP[d]. SP[d] is slightly slower than SP[a] for
all bins except the very first and very last, indicating a slight advantage of
processing small pipes before bigger ones on these instances. Interestingly,
SP[d] is also slower than both SP[d+c] and SP[d-c] for all bins. The fact that
these two variants have the same speed-ups indicates that EncapsulateAndJoin
should not be interleaved with the other operations, while it does not matter
whether it is handled first or last. Still, the variance in relative running
times is high and none of the variants is consistently faster on a larger part
of the instances. To summarize, the plots show a slight advantage for not
interleaving operation EncapsulateAndJoin with the others or sorting by
ascending degree, but this advantage is not significant in the statistical
sense; see Section 6.2. We keep SP[d] as the baseline for our further
analysis.

###  5.2. Pipes with two Block-Vertex Endpoints

Our baseline always processes pipes where both endpoints are block-vertices by
applying PropagatePQ or SimplifyMatching based on the embedding tree of an
arbitrary endpoint of the pipe. Alternatively, if the endpoints lie in
different connected components, such pipes can also be joined directly by
identifying their incident edges as in the second step of EncapsulateAndJoin.
This directly removes the pipe entirely instead of splitting into further
smaller pipes, although it also results in larger connected components. We
enable this joining in variant SP[d b]. As a second alternative, we may also
compute the embedding trees of both block-vertices and then propagate their
intersection. This preempts the multiple following operations propagating back
embedding information individually for each newly-created smaller pipe. We
enable this intersection in variant SP[d i]. Variant SP[d bi] combines both
variants, preferring the join and only intersecting if the endpoints are in
the same connected component. We compare the effect of differently handling
pipes with two block-vertex endpoints in variants SP[d b], SP[d i] and SP[d
bi] with the baseline SP[d], which computes the embedding tree for an
arbitrary endpoint and only joins pipes where both pipes are cut-vertices.

Figure 13(b) shows that SP[d b] (and similarly SP[d bi]) is faster by close to
25 on instances with less than $1000$ cluster-border edge crossings, but
quickly grows 5 times slower than SP[d] for larger instances. This effect is
also visible in the absolute values of Figure 11(a). This is probably caused
by the larger connected components (see the last column of Table 3), which
make the computation of embedding trees more expensive. Only inserting an
embedding tree instead of the whole connected component makes the embedding
information of the component directly available in a compressed form without
the need to later process the component in its entirety again. Figure 13(b)
also shows that SP[d i] is up to a third slower than SP[d], indicating that
computing both embedding trees poses a significant overhead while not yielding
sufficiently more information to make progress faster. We also evaluated
combinations of the variants from this section with the different orderings
from the previous section, but observed no notable differences in running time
behavior. The effects of the variants from this section always greatly
outweigh the effects from the different orderings. To summarize, as the plots
only show an advantage of differently handling pipes between block-vertices
for small instances, but some strong disadvantages especially for larger
instances, we keep SP[d] as our baseline.

(a)

(b)

Figure 14.  Relative running times for (a) SPQR-tree batched embedding tree
generation and (b) for different variants thereof.

###  5.3. Batched Embedding Tree Generation

Our preliminary analysis showed that the computation of embedding trees
consumes a large fraction of the running time (see Figure 10), which cannot be
reduced significantly by using the degrees of freedom of the algorithm studied
in the previous two sections. To remedy the overhead of recomputing embedding
trees multiple times we now change the algorithm to no longer process pipes
one-by-one, but to process all pipes of a biconnected component in one batch.
This is facilitated by an alternative approach for generating embedding trees
not only for a single vertex, but for all vertices of a biconnected component.
The embedding tree of a vertex $v$ can be derived from the SPQR-tree using the
approach described by Bläsius et al. (br-spo-16, ): Each occurrence of $v$ in
a “parallel” skeleton of the SPQR-tree corresponds to a (PQ-tree) P-node in
the embedding tree of $v$, each occurrence in a “rigid” to a (PQ-tree) Q-node.
This derivation can be done comparatively quickly, in time linear in the
degree of $v$. Thus, once we have the SPQR-tree of a biconnected component
available, we can apply all currently feasible PropagatePQ and
SimplifyMatching operations in a single batch with little overhead. The SPQR-
tree computation takes time linear in the size of the biconnected component,
albeit with a larger linear factor than for the linear-time planarity test
that yields only a single embedding tree. In a direct comparison with the
planarity test, this makes the SPQR-tree the more time-consuming approach.

We enable the batched embedding tree computation based on SPQR-trees in
variant SP[s]. Figures 14(a) and 11(a) show that for small instances, this
yields a slowdown of close to a third. Showing a behavior inverse to SP[d b],
SP[s] grows faster for larger instances and its speed-up even increases to up
to 4 times as fast as the baseline SP[d]. This makes SP[s] the clear champion
of all variants considered so far. We will thus use it as baseline for our
further evaluation, where we combine SP[s] with other, previously considered
flags.

###  5.4. SPQR-Batch Variations

Figure 14(b) switches the baseline between the two variants shown in Figure
14(a) and additionally contains combinations of the variants from Section 5.2
with the SPQR-batch computation. As in Figure 13(b), the intersection of
embedding trees in SP[s i] is consistently slower, albeit with a slightly
smaller margin. The joining of blocks in SP[s b] also shows a similar behavior
as before, starting out 25 faster for small instances and growing up to 100
slower for larger instances. Again, this is probably because too large
connected components negatively affect the computation of SPQR-trees. Still,
the median of SP[s b] is consistently faster than SP[d]. Different to before,
SP[s bi] is now faster than SP[s b], making it the best variant for instances
with up to $5000$ cluster-border edge crossings. This is probably because in
the batched mode, there is no relevant overhead for obtaining a second
embedding tree, while the intersection does preempt some following operations.
To summarize, for instances up to size $5000$, SP[s bi] is the fastest
variant, which is outperformed by SP[s] on larger instances. This can also be
seen in the absolute running times in Figure 11(a), where SP[s] is more than
an order of magnitude faster than SP[d b] on large instances.

##  6\. Further Analysis

In this section, we provide further in-depth analysis of the different
variants from the previous section and also analyze their performance on the
remaining datasets to give a conclusive judgement. To gain more insights into
the runtime behavior, we measured the time each individual step of the
algorithm takes when using the different variants. An in-depth analysis of
this data is given in Section 6.1, where Figure 15 also gives a more detailed
visualization of per-step timings. The per-step data corroborates that the
main improvement of faster variants is greatly reducing the time spent on the
generation of embedding trees, at the cost of slightly increased time spent on
the solve and embed phases.

To further verify our ranking of variants’ running times from the previous
sections, we also use a statistical test to check whether one variant is
significantly faster than another. The results presented in Section 6.2
corroborate our previous results, showing that pipe ordering has no
significant effect while the too large connected components and batched
processing of pipes using SPQR-trees significantly change the running time.

The results of the remaining datasets SEFE-LRG and SP-LRG are presented in
Section 6.3 and mostly agree with the results on C-LRG, with SP[d b] clearly
being the slowest and SP[s] being the fastest on large instances. The main
difference is the magnitude of the overhead generated by large connected
components for variants with flag [b].

Mode |  Total Time |  Make Reduced |  Solve Reduced |  Embed |  Enc.And-Join |  Propagate |  Simplify |  Compute Emb. Tree |  Undo Simplify |  #Simplify Operations |  Max. Bicon. Size
---|---|---|---|---|---|---|---|---|---|---|---
SP[d] | $142.68$ | $133.08$ | $0.82$ | $8.78$ | $0.25$ | $5.00$ | $13.79$ | $91.34$ | $5.64$ | $1811$ | $2780$
SP[d b] | $197.17$ | $194.72$ | $0.99$ | $1.46$ | $0.63$ | $1.36$ | $1.53$ | $186.18$ | $0.42$ | $652$ | $13\,021$
SP[s] | $86.57$ | $57.75$ | $1.25$ | $27.56$ | $0.57$ | $9.84$ | $22.38$ | $7.61$ | $18.03$ | $2696$ | $2890$
SP[s b] | $93.07$ | $79.25$ | $3.55$ | $10.26$ | $2.92$ | $4.29$ | $12.74$ | $46.31$ | $5.46$ | $1421$ | $22\,965$
SP[s bi] | $81.32$ | $68.90$ | $3.09$ | $9.32$ | $2.51$ | $3.79$ | $11.52$ | $41.16$ | $4.84$ | $1448$ | $23\,284$

Table 3.  Average values for different variants of SP on dataset C-LRG. All
values, except for the counts in the last two columns, are running times in
seconds. The first data column shows the average total running time, followed
by how this is split across the three phases. The following four columns show
the composition of the running time of the “Make Reduced” step. The last three
columns detail information about the “Undo Simplify” step in the “Embed”
phase, and the maximum size of biconnected components in the reduced instance.

Figure 15. The average running time of our different Synchronized Planarity
variants.

###  6.1. Detailed Runtime Profiling

Table 3 shows the per-step running time information aggregated for variants
studied in the previous section. Figure 15 in greater detail shows how the
running time spent is split on average across the different steps of the
algorithm (Figure 15) and then also further drills down on the composition of
the individual steps that make the instance reduced (Figure 15), solve the
reduced instance (Figure 15), and then derive a solution and an embedding for
the input instance by undoing all changes while maintaining the embedding
(Figure 15). For variants that use the SPQR-tree for embedding information
generation, we also analyze the time spent on the steps of this batch
operation (Figure 15). Note that we do not have these measurements available
for runs that timed out. To ensure that the bar heights still correspond to
the actual overall running times in the topmost plot, we add a bar
corresponding to the time consumed by timed-out runs on top. This way,
ordering the bars by height yields roughly the same order of variants as we
already observed in Figure 11(a).

Figure 15 clearly shows that the majority of time during the reduce step is
spent on generating embedding information, either in the form of directly
computing embedding trees (bars prefixed with “ET”) or by computing SPQR
trees. This can also be seen by comparing column “Make Reduced” in Table 3
with column “Compute Emb Tree”. Only for the fastest variants, those with flag
[s] and without [b], the execution of the actual operations of the algorithm
becomes more prominent over the generation of embedding information in Figure
15. Here, the terminal case of the SimplifyMatching operation (described in
the bottom left part of Figure 5) now takes the biggest fraction of time, and
actually also a bigger absolute amount of time than for the other, slower
variants with flag [b] enabled. This is probably because, instead of being
joined as with flag [b] enabled, here pipes between block-vertices are split
by PropagatePQ into multiple smaller pipes, which then need to be removed by
SimplifyMatching. This leads to the variants without [b] needing, on average,
roughly two to three times as many SimplifyMatching applications as those with
[b]; see Table 3.

The larger biconnected components caused by [b] may also be the reason why the
insertion of wheels takes a larger amount of time for variants with [b] in the
solving phase shown in Figure 15. When replacing a cut-vertex by a wheel, all
incident biconnected components with at least two edges incident to the cut-
vertex get merged. Updating the information stored with the vertices of the
biconnected components is probably consuming the most time here, as undoing
the changes by contracting the wheels is again very fast. Other than the
“MakeWheels” part, most time during the solving phase is spent on computing
SPQR trees, although both is negligible in comparison to the overall running
time.

The running times of the embedding phase given in Figure 15 show an
interesting behavior as they increase when the “Make Reduced” phase running
time decreases, indicating a potential trade-off to be made; see also the
“Embed” column in Table 3. As the maximum time spent on the “Make Reduced”
phase is still slightly larger, variants where this phase is faster while the
embedding phase is slower are still overall the fastest. The biggest
contribution of running time in the latter phase is the undoing of
SimplifyMatching operations, which means copying the embedding of one endpoint
of a removed pipe to the other. The time spent here roughly correlates with
the time spent on applying the SimplifyMatching operations in the first place
(see Table 3).

To summarize, the per-step data corroborates that the main improvement of
faster variants is greatly reducing the time spent on the generation of
embedding trees, at the cost of slightly increased time spent on the solve and
embed phases. Flags [s] and [b] have the biggest impact on running times,
while flag [i] and the processing order of pipes do not seem to have a
significant influence on the overall running time. While the variants with [s]
clearly have the fastest overall running times, there is some trade-off
between the amounts of time spent on different phases of the algorithm when
toggling the flag [b].

###  6.2. Statistical Significance

To test whether one variant is (in the statistical sense) significantly faster
than another, we use the methodology proposed by Radermacher (rad-ggd-20, ,
Section 3.2) for comparing the performance of graph algorithms. For a given
graph $G$ and two variants of the algorithm described by their respective
running times $f_{A}(G),f_{B}(G)$ on $G$, we want to know whether we have a
likelihood at least $p$ that the one variant is faster than the other by at
least a factor $\Delta$. To do so, we use the binomial sign test with
advantages as used by Radermacher (rad-ggd-20, ), where we fix two values
$p\in[0,1]$ and $\Delta\geq 1$, and study the following hypothesis given a
random graph $G$ from our dataset: Inequality $f_{A}(G)\cdot\Delta<f_{B}(G)$
holds with probability $\pi$, which is at least $p$. The respective null
hypothesis is that the inequality holds with probability less than $p$. Note
that this is an experiment with exactly two outcomes (the inequality holding
or not), which we can independently repeat on a sequence of $n$ graphs and
obtain the number of instances $k$ for which the inequality holds. Using the
binomial test, we can check the likelihood of obtaining at most $k$ successes
by drawing $n$ times from a binomial distribution with probability $p$. If
this likelihood is below a given significance level $\alpha\in[0,1]$, that is
the obtained result is unlikely under the null hypothesis, we can reject the
null hypothesis that the inequality only holds with a probability less than
$p$.

Fixing the significance level to the commonly-used value $\alpha=0.05$, we
still need to fix values for $p$ and $\Delta$ to apply this methodology in
practice. We will use three different values for $p\in[0.25,0.5,0.75]$,
corresponding to the advantage on a quarter, half, and three quarters of the
dataset. To obtain values for $\Delta$, we will split our datasets evenly into
two halves $\mathcal{G}_{\text{train}}$ and $\mathcal{G}_{\text{verify}}$,
using the $\mathcal{G}_{\text{train}}$ to obtain an estimate for $\Delta$ and
$\mathcal{G}_{\text{verify}}$ to verify this value. For a given value of $p$,
we set $\Delta^{\prime}$ to the largest value such that
$f_{A}(G)\cdot\Delta^{\prime}<f_{B}(G)$ holds for
$p\cdot|\mathcal{G}_{\text{train}}|$ instances. To increase the likelihood
that we can reject the null hypothesis in the verification step on
$\mathcal{G}_{\text{verify}}$, we will slightly discount the obtained value of
$\Delta^{\prime}$, using $\Delta=\min(1,c\cdot\Delta^{\prime})$ instead with
$c$ set to $0.75$.

Figure 16.  Advantages of variants without flag [s] on C-LRG instances of size
at least $5000$. Blue cell backgrounds indicate significant values, while in
cells with white background, we were not able to reject the null-hypothesis
with significance $\alpha=0.05$. Empty cells indicate that the fraction where
the one algorithm is better than the other is smaller than $p$.

Applying this methodology, Figure 16 compares the pairwise advantages of the
variants from Sections 5.1 and 5.2. We see that SP[d i] and especially SP[d b]
are significantly slower than the other variants: for the quarter of the
dataset with the most extreme differences, the advantage rises up to a 5-fold
speed-up for other variants, while slight advantages still persist when
considering three quarters of instances. Conversely, not even on a quarter of
instances are SP[d i] and SP[d b] faster than other variants. Comparing the
remaining variants with each other, we see that each variant has at least a
quarter of instances where it is slightly faster than the other variants, but
always with no noticeable advantage, that is $\Delta=1$. This is not
surprising as the relative running times are scattered evenly above and below
the baseline in Figure 13(a). For half of the dataset, SP[d-c] is still
slightly faster than other variants, while no variant from Section 5.1 is
faster than another for at least three quarters of instances. To summarize,
our results here corroborate the findings from Sections 5.1 and 5.2, with SP[d
i] and SP[d b] as the clearly slowest variants. While there is no clear winner
among the other variants, at least SP[d-c] is slightly faster than the others
on half of the dataset, but still has no noticeable advantage.

(a)

(b)

Figure 17.  Advantages of variants with flag [s] on C-LRG instances of size at
least $5000$ (a) and at most (b) $5000$.

Figures 17(a) and 17(b) compare the pairwise advantages of the variants from
Sections 5.3 and 5.4 (see also Figure 14(b)) for instances with more and less
than $5000$ cluster-border edge crossings, respectively. For the larger
instances of Figure 17(a), the variants with flag [s] outperform SP[d] on at
least 75 of instances, with advantages as high as a factor of 5 on at least a
quarter of instances. Furthermore, SP[s] outperforms the variants with
additional flags [b] and [i] on at least half of all instances. Considering 75
of all instances, the only significant result is that SP[s bi] outperforms
SP[s b] but with no advantage, i.e. $\Delta=1$. For the smaller instances of
Figure 17(b), the comparison looks vastly different. Here, SP[s bi]
outperforms all other variants on at least 75 of instances, although its
advantage is not large, with only up to $1.6$ even on the most extreme quarter
of the dataset. Furthermore, variants SP[d] and SP[s b] outperform variants
SP[s i] and SP[s] on half of the dataset, but again with no noticeable
advantage, that is $\Delta=1$. To summarize, our results are again in
accordance with those from Sections 5.3 and 5.4, where for large instances
variant SP[s] is the fastest, whereas for smaller instances SP[s bi] is
superior.

(a)

(b)

Figure 18.  Absolute (a) and relative (b) running times with regard to SP[d]
for C-LRG.

(c)

(d)

Figure 19.  Absolute (a) and relative (b) running times with regard to SP[d]
for SP-LRG.

(a)

(b)

Figure 20.  Absolute (a) and relative (b) running times with regard to SP[d]
for SEFE-LRG.

###  6.3. Other Problem Instances

Running the same evaluation on the datasets SEFE-LRG and SP-LRG yielded
absolute running times with roughly the same orders of magnitude as for C-LRG,
see the left plots in Figures 20, 20 and 20 (but note that the plots show
different ranges on the x-axis while having the same scale on the y-axis). The
right plots in the figures again detail the running times relative to SP[d].
For SP-LRG, the relative running time behavior is similar to the behavior
observed on C-LRG. The two major differences concern variants with flag [b].
Variant SP[d b(i)] is not faster than SP[d] on small instances and also sooner
grows slower on large instances. Similarly, SP[s b(i)] is not much faster than
SP[d] on small instances, and its speed-up over SP[d] for larger instances has
a dent where it returns to having roughly the same speed as SP[d] around size
1000. On a large scale, this behavior indicates that the slowdown caused by
large connected components is even worse in dataset SP-LRG. For SEFE-LRG, the
instances are less evenly distributed in terms of their total pipe degree, as
the total pipe degree directly corresponds to the vertex degrees in the SEFE
instance. Regarding the relative running time behavior, we still see that SP[d
bi] is much slower and SP[s (i)] much faster than SP[d]. For the remaining
variants, the difference to SP[d] is much smaller than in the two other
datasets. This indicates that the size of connected components does not play
an as important role in this dataset as before.

##  7\. Conclusion

In this paper, we described the first practical implementation of Synchronized
Planarity, which generalizes many constrained planarity problems such as
Clustered Planarity and Connected SEFE. We evaluated it on more than $28\,000$
instances stemming from different problems. Using the quadratic algorithm by
Bläsius et al. (bfr-spw-21, ), instances with 100 vertices are solved in
milliseconds, while we can still solve most instances with up to $100\,000$
vertices within minutes. This makes our implementation at least an order of
magnitude faster than all other Clustered Planarity implementations, which
also have a worse asymptotic running time. Furthermore, we found incorrect
results in one of the other implementations. Analyzing our running times in
more detail, we find the generation of embedding information in the form of
embedding trees to be by far the most time-consuming, while the actual
operations of the algorithm that reduce and solve the instance are
comparatively fast. We apply algorithm engineering and use the various degrees
of freedom of the algorithm to speed up computation times by up to an order of
magnitude. The main result here is that the batched computation of embedding
information we devise using SPQR-trees produces a major speed-up. Tuning some
other variables produces a speed-up only in parts of the algorithm while
slowing down others, showing that further speed-ups may be more challenging to
achieve and that trade-offs may have to be made. One possible approach could
be implementing the dynamically-maintained SPQR-tree described by Fink and
Rutter (fr-mtc-23, ), which also yields a further theoretical speed-up. As
contribution towards future work in the field of graph drawing, we also see
that our implementation can be used as reference for the implementation of
more specialized, but potentially faster constrained planarity algorithms,
which proved challenging in the past (brue-pvf-21, ).

## References

  * (1) P. Angelini, M. D. Bartolomeo, and G. D. Battista.  Implementing a partitioned 2-page book embedding testing algorithm.  In W. Didimo and M. Patrignani, editors, Graph Drawing - 20th International Symposium, GD 2012, Redmond, WA, USA, September 19-21, 2012, Revised Selected Papers, volume 7704 of Lecture Notes in Computer Science, pages 79–89. Springer, 2012.  doi:10.1007/978-3-642-36763-2_8.
  * (2) P. Angelini, G. D. Battista, F. Frati, V. Jelínek, J. Kratochvíl, M. Patrignani, and I. Rutter.  Testing planarity of partially embedded graphs.  ACM Transactions on Algorithms, 11(4):32:1–32:42, 2015.  doi:10.1145/2629341.
  * (3) P. Angelini, G. D. Battista, F. Frati, M. Patrignani, and I. Rutter.  Testing the simultaneous embeddability of two graphs whose intersection is a biconnected or a connected graph.  Journal of Discrete Algorithms, 14:150–172, 2012.  doi:10.1016/j.jda.2011.12.015.
  * (4) P. Angelini and G. Da Lozzo.  Clustered planarity with pipes.  Algorithmica, 81(6):2484–2526, 2019.  doi:10.1007/s00453-018-00541-w.
  * (5) P. Angelini and G. D. Lozzo.  SEFE = C-Planarity?  The Computer Journal, 59(12):1831–1838, 2016.  doi:10.1093/comjnl/bxw035.
  * (6) P. Angelini, G. D. Lozzo, and D. Neuwirth.  Advancements on SEFE and partitioned book embedding problems.  Theoretical Computer Science, 575:71–89, 2015.  doi:10.1016/j.tcs.2014.11.016.
  * (7) C. Bachmaier.  Circle planarity of level graphs.  PhD thesis, University of Passau, Germany, 2004.  URL: http://www.opus-bayern.de/uni-passau/volltexte/2004/38/index.html.
  * (8) T. Bläsius, S. D. Fink, and I. Rutter.  Synchronized planarity with applications to constrained planarity problems.  ACM Transactions on Algorithms, 19(4), 2023.  doi:10.1145/3607474.
  * (9) T. Bläsius, S. G. Kobourov, and I. Rutter.  Simultaneous embedding of planar graphs.  In R. Tamassia, editor, Handbook on Graph Drawing and Visualization, pages 349–381. Chapman and Hall/CRC, 2013.  URL: https://cs.brown.edu/people/rtamassi/gdhandbook/chapters/simultaneous.pdf.
  * (10) T. Bläsius and I. Rutter.  Disconnectivity and relative positions in simultaneous embeddings.  Computational Geometry, 48(6):459–478, 2015.  doi:10.1016/j.comgeo.2015.02.002.
  * (11) 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.05673, doi:10.1016/j.tcs.2015.10.011.
  * (12) T. Bläsius and I. Rutter.  Simultaneous PQ-ordering with applications to constrained embedding problems.  ACM Transactions on Algorithms, 12(2):16:1–16:46, 2016.  doi:10.1145/2738054.
  * (13) 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.
  * (14) J. M. Boyer, P. F. Cortese, M. Patrignani, and G. D. Battista.  Stop minding your p’s and q’s: Implementing a fast and simple DFS-based planarity testing and embedding algorithm.  In Graph Drawing, pages 25–36. Springer Berlin Heidelberg, 2004\.  doi:10.1007/978-3-540-24595-7_3.
  * (15) P. Brass, E. Cenek, C. A. Duncan, A. Efrat, C. Erten, D. P. Ismailescu, S. G. Kobourov, A. Lubiw, and J. S. Mitchell.  On simultaneous planar graph embeddings.  Computational Geometry, 36(2):117–130, 2007.  doi:10.1016/j.comgeo.2006.05.006.
  * (16) G. Brückner.  Planarity Variants for Directed Graphs.  PhD thesis, Karlsruhe Institute of Technology, Germany, 2021.  URL: https://nbn-resolving.org/urn:nbn:de:101:1-2021080405022988868936.
  * (17) M. Chimani, C. Gutwenger, M. Jansen, K. Klein, and P. Mutzel.  Computing maximum c-planar subgraphs.  In I. G. Tollis and M. Patrignani, editors, Graph Drawing, 16th International Symposium, GD 2008, Heraklion, Crete, Greece, September 21-24, 2008. Revised Papers, volume 5417 of Lecture Notes in Computer Science, pages 114–120. Springer, 2008.  doi:10.1007/978-3-642-00219-9_12.
  * (18) M. Chimani, C. Gutwenger, M. Jünger, G. W. Klau, K. Klein, and P. Mutzel.  The open graph drawing framework (OGDF).  In R. Tamassia, editor, Handbook on Graph Drawing and Visualization, pages 543–569. Chapman and Hall/CRC, 2013.  URL: https://cs.brown.edu/people/rtamassi/gdhandbook/chapters/ogdf.pdf.
  * (19) M. Chimani and K. Klein.  Shrinking the search space for clustered planarity.  In W. Didimo and M. Patrignani, editors, Graph Drawing - 20th International Symposium, GD 2012, Redmond, WA, USA, September 19-21, 2012, Revised Selected Papers, volume 7704 of Lecture Notes in Computer Science, pages 90–101. Springer, 2012.  doi:10.1007/978-3-642-36763-2_9.
  * (20) P. F. Cortese, G. Di 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.
  * (21) G. Da Lozzo.  Planar Graphs with Vertices in Prescribed Regions:models, algorithms, and complexity.  PhD thesis, Roma Tre University, 2015.  URL: http://www.dia.uniroma3.it/~dalozzo/files/phd-thesis-giordano-dalozzo.pdf.
  * (22) G. Di Battista and R. Tamassia.  On-line maintenance of triconnected components with SPQR-trees.  Algorithmica, 15(4):302–318, 1996.  doi:10.1007/bf01961541.
  * (23) M. Elf, C. Gutwenger, M. Jünger, and G. Rinaldi.  Branch-and-Cut Algorithms for Combinatorial Optimization and Their Implementation in ABACUS, pages 157–222.  Springer Berlin Heidelberg, Berlin, Heidelberg, 2001.  doi:10.1007/3-540-45586-8_5.
  * (24) A. Estrella-Balderrama, J. J. Fowler, and S. G. Kobourov.  Graphset, a tool for simultaneous graph drawing.  Software: Practice and Experience, 40(10):849–863, 2010.  doi:10.1002/spe.958.
  * (25) 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.
  * (26) S. D. Fink, M. Pfretzschner, and I. Rutter.  Experimental comparison of pc-trees and pq-trees.  ACM Journal of Experimental Algorithmics, 28, 2023.  doi:10.1145/3611653.
  * (27) S. D. Fink and I. Rutter.  Maintaining triconnected components under node expansion.  In Proceedings of the 13th International Conference on Algorithms and Complexity (CIAC 23), 2023.  doi:10.1007/978-3-031-30448-4_15.
  * (28) H. D. Fraysseix, P. O. D. Mendez, and P. Rosenstiehl.  Trémaux trees and planarity.  International Journal of Foundations of Computer Science 17 (5) (2006) 1017-1029, 2006.  arXiv:math/0610935, doi:10.1142/S0129054106004248.
  * (29) 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.
  * (30) R. Fulek, M. J. Pelsmajer, M. Schaefer, and D. Štefankovič.  Hanani–tutte, monotone drawings, and level-planarity.  In Thirty Essays on Geometric Graph Theory, pages 263–287. Springer New York, 2012.  doi:10.1007/978-1-4614-0110-0_14.
  * (31) R. Fulek and C. D. Tóth.  Atomic embeddability, clustered planarity, and thickenability.  Journal of the ACM, 69(2):13:1–13:34, 2022.  arXiv:1907.13086v1, doi:10.1145/3502264.
  * (32) E. Gassner, M. Jünger, M. Percan, M. Schaefer, and M. Schulz.  Simultaneous graph embeddings with fixed edges.  In Graph-Theoretic Concepts in Computer Science, pages 325–335. Springer Berlin Heidelberg, 2006.  doi:10.1007/11917496_29.
  * (33) A. V. Goldberg and R. E. Tarjan.  A new approach to the maximum-flow problem.  Journal of the ACM, 35(4):921–940, 1988.  doi:10.1145/48014.61051.
  * (34) 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.
  * (35) C. Gutwenger and P. Mutzel.  A linear time implementation of SPQR-trees.  In Proceedings of the 8th International Symposium on Graph Drawing (GD’20), pages 77–90. Springer, 2001.  doi:10.1007/3-540-44541-2_8.
  * (36) C. Gutwenger, P. Mutzel, and M. Schaefer.  Practical experience with hanani-tutte for testing c-planarity.  In C. C. McGeoch and U. Meyer, editors, 2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments, ALENEX 2014, Portland, Oregon, USA, January 5, 2014, pages 86–97. SIAM, 2014.  doi:10.1137/1.9781611973198.9.
  * (37) M. Harrigan and P. Healy.  Practical level planarity testing and layout with embedding constraints.  In S. Hong, T. Nishizeki, and W. Quan, editors, Graph Drawing, 15th International Symposium, GD 2007, Sydney, Australia, September 24-26, 2007. Revised Papers, volume 4875 of Lecture Notes in Computer Science, pages 62–68. Springer, 2007.  URL: https://doi.org/10.1007/978-3-540-77537-9_9, doi:10.1007/978-3-540-77537-9\\_9.
  * (38) S.-H. Hong and H. Nagamochi.  Two-page book embedding and clustered graph planarity.  Technical Report TR[2009-004], 2009.  URL: https://citeseerx.ist.psu.edu/doc/10.1.1.361.1233.
  * (39) M. Jünger, S. Leipert, and P. Mutzel.  Level planarity testing in linear time.  In S. Whitesides, editor, Graph Drawing, 6th International Symposium, GD’98, Montréal, Canada, August 1998, Proceedings, volume 1547 of Lecture Notes in Computer Science, pages 224–237. Springer, 1998.  doi:10.1007/3-540-37623-2_17.
  * (40) S. Leipert.  Level planarity testing and embedding in linear time.  PhD thesis, Universität zu Köln, 1998.
  * (41) T. Lengauer.  Hierarchical planarity testing algorithms.  Journal of the ACM, 36(3):474–509, 1989.  doi:10.1145/65950.65952.
  * (42) M. Patrignani.  Planarity testing and embedding.  In R. Tamassia, editor, Handbook on Graph Drawing and Visualization, pages 1–42. Chapman and Hall/CRC, 2013.  URL: https://cs.brown.edu/people/rtamassi/gdhandbook/chapters/planarity.pdf.
  * (43) H. C. Purchase, J.-A. Allder, and D. Carrington.  Graph layout aesthetics in UML diagrams: User preferences.  Journal of Graph Algorithms and Applications, 6(3):255–279, 2002\.  doi:10.7155/jgaa.00054.
  * (44) M. Radermacher.  Geometric Graph Drawing Algorithms - Theory, Engineering and Experiments.  PhD thesis, Karlsruher Institut für Technologie (KIT), 2020.  doi:10.5445/IR/1000117664.
  * (45) B. Randerath, E. Speckenmeyer, E. Boros, P. L. Hammer, A. Kogan, K. Makino, B. Simeone, and O. Cepek.  A satisfiability formulation of problems on level graphs.  Electron. Notes Discret. Math., 9:269–277, 2001.  doi:10.1016/S1571-0653(04)00327-0.
  * (46) I. Rutter.  Simultaneous embedding.  In S.-H. Hong and T. Tokuyama, editors, Beyond Planar Graphs, pages 237–265. Springer Singapore, 2020.  doi:10.1007/978-981-15-6533-5_13.
  * (47) 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.
  * (48) C. Ware, H. Purchase, L. Colpoys, and M. McGill.  Cognitive measurements of graph aesthetics.  Information Visualization, 1(2):103–110, jun 2002.  doi:10.1057/palgrave.ivs.9500013.