Atomic Embeddability, Clustered Planarity, and Thickenability,

Rado Fulek and Csaba Tóth announce a polynomial time algorithm for clustered planarity (given a graph and a hierarchical clustering of its vertices, draw the graph planarly with clusters as simple closed curves and no unnecessary cluster-edge crossings).

If this holds up, it's big: the problem has been open since 1995 and a lot of people have worked on it with only modest progress until now.

Sign in to participate in the conversation

The social network of the future: No ads, no corporate surveillance, ethical design, and decentralization! Own your data with Mastodon!