Information Technology Reference
In-Depth Information
A New Perspective on Clustered Planarity
as a Combinatorial Embedding Problem
Thomas BläsiusandIgnaz Rutter
Faculty of Informatics, Karlsruhe Institute of Technology(KIT),Germany
{blaesius,rutter}@kit.edu
Abstract.
The clustered planarity problem (c-planarity) asks whether a hierar-
chically clustered graph admits a planar drawing such that the clusters can be
nicely represented by regions. We introduce the cd-tree data structure and give a
new characterization of c-planarity. It leads to efficient algorithms for c-planarity
testing in the following cases. (i) Every cluster and every co-cluster has at most
two connected components. (ii) Every cluster has at most five outgoing edges.
Moreover, the cd-tree reveals interesting connections between c-planarity and
planarity with constraints on the order of edges around vertices. On one hand,
this gives rise to a bunch of new open problems related to c-planarity, on the
other hand it provides a new perspective on previousresults.
1
Introduction
When visualizinggraphs whose nodes are structured in a hierarchy, one usually has two
objectives. First, the graph should be drawn nicely. Second, the hierarchical structure
should be expressed by the drawing.Regarding the first objective, we require drawings
withoutedge crossings, i.e.,
planardrawings
.Anatural way to represent a cluster is a
simple region containing exactly the vertices in the cluster. To express the hierarchical
structure, the boundaries of two regions must not cross and edges of the graph can cross
region boundaries at most once (if only one of its endpoints lies inside the cluster).
Such a drawing is called
c-planar
; see Sec. 2 for a formal definition. Testing aclustered
graph for c-planarity is a fundamental open problem in the field of Graph Drawing.
C-planarity was first considered by Lengauer [21] (in a different context). He gave
an efficient algorithm for the case that every cluster is connected. Feng et al. [13], who
coined the name c-planarity, rediscovered the problem and gave a similar algorithm.
Cornelsen and Wagner [7] showed that c-planarity is equivalent to planarity when addi-
tionally every co-cluster is connected.
Relaxing the condition that every cluster must be connected, makes testing c-planarity
surprisingly difficult. Efficient algorithms are known only for very restricted cases and
many of these algorithms are very involved. One example is the efficient algorithm by
Jelínek et al. [17, 18] for the case that every cluster consists of at most two connected
components while the planar embedding of the graph is fixed. Another algorithm by
Jelínek et al. [19] solves the case that every cluster has at most fouroutgoing edges.
Partly done within GRADR - EUROGIGA project no. 10-EuroGIGA-OP-003. Supported by a
fellowship within the Postdoc-Program of the German Academic Exchange Service (DAAD).
