Clustered Planarity Testing Revisited - Graph Drawing - page 427

Clustered Planarity Testing Revisited

Radoslav Fulek 1 , 4 , ,JanKyncl 1 , ,Igor Malinovic 2 ,andDom otor Palv olgyi 3 ,

1

Department of Applied Mathematics and Institute for Theoretical Computer Science,
Faculty of Mathematics and Physics, Charles University, Malostransk´enam. 25,
118 00 Praha 1, Czech Republic
[e-mail] , [e-mail]

Faculte InformatiqueetCommunications, Ecole PolytechniqueFederale de Lausanne,
1015 Lausanne, Switzerland
[e-mail]

2

3

Institute of Mathematics, Eotvos University, Pazmany Peter setany 1/C,
H-1117 Budapest, Hungary
[e-mail]

4

Department of Industrial Engineering and Operations Research, Columbia University,
New York City, NY, USA

Abstract. The Hanani-Tutte theorem is a classical result proved for the first time
in the 1930s that characterizes planar graphs as graphs that admit a drawing in
the plane in which every pair of edges not sharing a vertex cross an even number
of times. We generalize this classical result to clustered graphs with two disjoint
clusters, and show that a straightforward extension of ourresult to flat clustered
graphs with three or more disjoint clusters is not possible.
We also give a new and short proof for a related result by Di Battista and Frati
based on the matroid intersection algorithm.

1 Introduction

Investigation of graph planarity can be traced back to the 1930s and developments ac-
complished at that time by Hanani [21], Kuratowski [26], Whitney [38] and others.
Forty years later, with the advent of computing machinery, a linear time algorithm for
graph planarity was discovered [23]. Nowadays, a polynomial time algorithm for testing
whether a graph admits a crossing-free drawing in the plane could almost be considered
a folklore result.
Nevertheless, many variants of planarity are still only poorly understood. As a con-
sequence of this state of affairs, the corresponding decision problem for these variants
has neither been shown to be polynomial nor NP -hard. Clustered planarity is one of

The author gratefully acknowledges support from the Swiss National Science Foundation
Grant No. 200021-125287/1 and ESF Eurogiga project GraDR as GA CR GIG/11/E023.
Supported by the ESF Eurogiga project GraDR as GA CR GIG/11/E023 and by the grant
SVV-2013-267313 (Discrete Models and Algorithms).
Supported by Hungarian National Science Fund (OTKA), under grant PD 104386 and un-
der grant NN 102029 (EUROGIGA project GraDR 10-EuroGIGA-OP-003) and the Janos
Bolyai Research Scholarship of the Hungarian Academy of Sciences.