A New Perspective on Clustered Planarity as a Combinatorial Embedding Problem - Graph Drawing - page 440

A popular restriction is to require a flat hierarchy, i.e., every pair of clusters has
empty intersection. For example, Di Battista and Frati [12] solve the case where the
clustering is flat, the graph has a fixed embedding and the faces have size at most 5.
Sec. 4.1 and Sec. 4.2 contain additional related work viewed from the new perspective.

Contribution and Outline. We first present the cd-tree data structure (Sec. 3) and use it
to characterize c-planarity in terms of combinatorial embeddingsofplanargraphs. This
provides a useful new perspective and significantly simplifies some previousresults.
In Sec. 4 we define different constrained-planarity problems. We show in Sec. 4.1
that they are equivalent to different variants of the c-planarity problem of flat-clustered
graphs. We also discuss which cases of the constrained embedding problems are solved
by previousresults on c-planarity. Based on these insights we derive a generic algorithm
for testing c-planarity in Sec. 4.2 and discuss previous work in this context.
In Sec. 5, we show how the cd-tree characterization together with results on the prob-
lem S IMULTANEOUS PQ-O RDERING [4] lead to efficient algorithms for the cases that
(i) every cluster and every co-cluster consists of at most two connected components; or
(ii) every cluster has at most five outgoing edges. The latter extends the result by Jelínek
et al. [19], where every cluster has at most fouroutgoing edges.

2 Preliminaries

We denote graphs by G with vertex set V and edgeset E . We implicitly assume graphs to
be simple (no multiple edges or loops). We use the prefix multi- to indicate that a graph
may have multiple edges (but no loops), e.g., a multi-cycle is obtained from a cycle by
multiplying edges. A (multi-)graph G is planar if it admits a planar drawing (no edge
crossings). The edge-ordering of a vertex v is the clockwise cyclic order of its incident
edges in a planar drawing of G .An embedding of G consists of an edge-ordering for
every vertex such that G has a planar drawing with these edge-orderings.
A PQ-tree [5] is an unrooted tree T with leaves L such that every inner node is either
a P-node or a Q-node . When embedding T , one can choose the edge-orderingsofP-
nodes arbitrarily, whereas the edge-orderings of Q-nodes are fixed up to reversal. Every
such embedding of T defines a cyclic order on the leaves L .ThePQ-tree Trepresents
the orders one can obtain in this way. A set of orders is PQ-representable if it can be
represented by a PQ-tree. The valid edge-orderings of non-cutvertices in planar graphs
are PQ-representable (e.g., [4]). Conversely, replace each Q-node of a PQ-tree T by
a wheel (to fix its edge-ordering) and connect all leaves to a new vertex v .Then T
represents the edge-orderingsof v in embeddingsoftheresultinggraph (e.g., [21]).

C-Planarity. A clustered graph ( G , T ) is a graph G together with a rooted tree T
whose leaves are the vertices of G .Let μ be a node of T .Thetree T μ is the subtree of

T consisting of the root and all its successors. The graph induced by the leaves of T μ

is a cluster in G . We identify this cluster with the node

μ

.Acluster is proper if it is
neither the whole graph (root cluster) nor a single vertex (leaf cluster).
A c-planardrawing of ( G , T ) is a planar drawing of G together with a simple
(= simply-connected) region R μ

μ

for every cluster μ satisfying the following properties.