The University of Arizona
Please note that this event has ended!

Atomic Embeddability, Clustered Planarity, and Thickenability

TRIPODS Seminar

Atomic Embeddability, Clustered Planarity, and Thickenability
Series: TRIPODS Seminar
Location: ENR2 S210
Presenter: Rado Fulek, University of Arizona, Computer Science
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.C-planarity 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 (c-planarity, for short) 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.
(Pizza, coffee & tea will be provided at 11:20am)