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. 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.

The 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.

Before our work, 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 Tóth.

computational geometrydiscrete mathematicscommutative algebracombinatorics

Audience: researchers in the topic

---

Copenhagen-Jerusalem Combinatorics Seminar

Series comments: There is a mailing list for talk announcements. If you want to receive the announcements, send an e-mail to the organizer to subscribe to the mailing list.

The password for the zoom room is 123456

---