Minimal disconnected cuts in planar graphs

Marcin Kamiński, Daniël Paulusma, Anthony Stewart, Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review


The problem of finding a disconnected cut in a graph is NP-hard in general but polynomial-time solvable on planar graphs. The problem of finding a minimal disconnected cut is also NP-hard but its computational complexity was not known for planar graphs. We show that it is polynomial-time solvable on 3-connected planar graphs but NP-hard for 2-connected planar graphs. Our technique for the first result is based on a structural characterization of minimal disconnected cuts in 3-connected K3,3 -free-minor graphs and on solving a topological minor problem in the dual. In addition we show that the problem of finding a minimal connected cut of size at least 3 is NP-hard for 2-connected apex graphs. Finally, we relax the notion of minimality and prove that the problem of finding a so-called semi-minimal disconnected cut is still polynomial-time solvable on planar graphs.

Original languageEnglish (US)
Pages (from-to)250-259
Number of pages10
Issue number4
StatePublished - Dec 1 2016


  • connectivity
  • planar graph
  • vertex cut

ASJC Scopus subject areas

  • Information Systems
  • Computer Networks and Communications


Dive into the research topics of 'Minimal disconnected cuts in planar graphs'. Together they form a unique fingerprint.

Cite this