Minimal disconnected cuts in planar graphs

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 is not known for planar graphs. We show that it is polynomial-time solvable on 3-connected planar graphs but NPhard 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. We show that the latter problem can be solved in polynomial-time even on general graphs. 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.

Original languageEnglish (US)
Title of host publicationFundamentals of Computation Theory - 20th International Symposium, FCT 2015, Proceedings
EditorsIgor Walukiewicz, Adrian Kosowski
PublisherSpringer Verlag
Number of pages12
ISBN (Print)9783319221762
StatePublished - 2015
Event20th International Symposium on Fundamentals of Computation Theory, FCT 2015 - Gdansk, Poland
Duration: Aug 17 2015Aug 19 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference20th International Symposium on Fundamentals of Computation Theory, FCT 2015

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


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

Cite this