My SODA talk slides on finding laminar 3-vertex separators of planar graphs are online:

At the talk, someone asked about finding a maximum set of laminar 3-separators. It's NP-complete: use Uehara's "NP-complete problems on a 3-connected cubic graph and their applications" ( to find cubic planar graphs whose ≤3-separators are vertex neighborhoods (so laminar separators = neighbors of independent vertices) in which maximum independent set is hard.

Sign in to participate in the conversation

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.