Follow

Atomic Embeddability, Clustered Planarity, and Thickenability, arxiv.org/abs/1907.13086

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
Mathstodon

A Mastodon instance for maths people. The kind of people who make \(\pi z^2 \times a\) jokes. Use \( and \) for inline LaTeX, and \[ and \] for display mode.