Follow

My SODA talk slides on finding laminar 3-vertex separators of planar graphs are online: ics.uci.edu/~eppstein/pubs/Epp

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" (jaist.ac.jp/~uehara/pdf/triang) 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
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.