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