Planar Multiway Cut with Terminals on Few Faces

Sukanya Pandey, Erik Jan van Leeuwen

We consider the \textsc{Edge Multiway Cut} problem on planar graphs. It is known that this can be solved in $n^{O(\sqrt{t})}$ time [Klein, Marx, ICALP 2012] and not in $n^{o(\sqrt{…