Clustered Planarity Testing Revisited
Date Change
Host
Applied Mathematics
Speaker
Radoslav Fulek
Columbia University
https://sites.google.com/site/fulekrado/
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 Topic
Discrete Applied Math Seminar