Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Math 269 - Combinatorics

Radoslav Fulek

University of Arizona

Atomic Embeddability, Clustered Planarity, and Thickenability

Abstract:

The planarity testing problem is the algorithmic problem of testing whether a given input graph is planar, that is, whether it can be drawn in the plane without edge crossings. Clustered planarity (c-planarity, for short) was introduced in 1995 by Feng, Cohen, and Eades as a generalization of graph planarity, in which the vertex set of the input graph is endowed with a hierarchical clustering and we seek an embedding (edge crossing-free drawing) of the graph in the plane that respects the clustering in a certain natural sense. A seemingly unrelated problem of thickenability for simplicial complexes emerged in the topology of manifolds in the 1960s. A 2-dimensional simplicial complex is thickenable if it embeds in some orientable 3-dimensional manifold. We study the atomic embeddability testing problem, which is a common generalization of clustered planarity and thickenability testing, and present a polynomial time algorithm for this problem, thereby giving the first polynomial time algorithm for c-planarity. Until now, it has been an open problem whether c-planarity can be tested efficiently, despite relentless efforts. Recently, Carmesin announced that thickenability can be tested in polynomial time. Our algorithm for atomic embeddability combines ideas from Carmesin's work with algorithmic tools previously developed for so-called weak embeddability testing. Joint work with Csaba Toth.

Host: Andrew Suk

December 12, 2019

2:00 PM

AP&M 6402

****************************