Close Menu

Clustered Planarity Testing Revisited

Date Change

When: 

Feb 4, 2015 - 4:40pm

Where: 

LS 152

Speaker: 

Radoslav Fulek
Columbia University

Description: 

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