Skip to Main content Skip to Navigation
Conference papers

Minimal Disconnected Cuts in Planar Graphs

Abstract : 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 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. 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.
Document type :
Conference papers
Complete list of metadata
Contributor : Dimitrios Thilikos Connect in order to contact the contributor
Submitted on : Friday, November 6, 2015 - 11:53:54 AM
Last modification on : Thursday, November 26, 2020 - 3:50:03 PM




Marcin Kaminski, Daniël Paulusma, Stewart Anthony, Dimitrios M. Thilikos. Minimal Disconnected Cuts in Planar Graphs. FCT: Fundamentals of Computation Theory, Aug 2015, Gdańsk, Poland. pp.243-254, ⟨10.1007/978-3-319-22177-9_19⟩. ⟨lirmm-01225549⟩



Record views