ICS Theory Group

Spring 2017: Theory Seminar
Bren Hall, Room 1423, 1:00pm


May 12, 2017:

Subexponential-Time Algorithm for Testing C-Planarity of Embedded Flat C-Graphs with Bounded Face Size

Sid Gupta

Abstract: We study the problem of testing clustered planarity for flat c-graphs with a fixed combinatorial embedding. In this setting, polynomial-time algorithms are known only for very restricted families of instances. We give the first subexponential-time algorithm for c-graphs with bounded face size. Our result is based on a divide-and-conquer approach and on exploiting a concise representation of the connectivity of each cluster.

Joint work with Giordano Da Lozzo, David Eppstein, and Michael T. Goodrich