Minimal Disconnected Cuts in Planar Graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2015

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.

Dates and versions

lirmm-01225549 , version 1 (06-11-2015)

Identifiers

Cite

Marcin J. 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⟩
119 View
0 Download

Altmetric

Share

Gmail Facebook X LinkedIn More