Close Menu

Clustered Planarity Testing Revisited

Date Change


Feb 4, 2015 - 4:40pm


LS 152


Radoslav Fulek
Columbia University


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 our result 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.

Joint work with J. Kyncl, I. Malinovic and D. Palvolgyi.

Event Type: 

Applied Mathematics - Discrete Applied Math Colloquia