@inproceedings{6ac367b5f7ea468083513c444eafd1e2,
title = "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 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.",
author = "Marcin Kami{\'n}ski and Dani{\"e}l Paulusma and Anthony Stewart and Thilikos, {Dimitrios M.}",
note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2015.; 20th International Symposium on Fundamentals of Computation Theory, FCT 2015 ; Conference date: 17-08-2015 Through 19-08-2015",
year = "2015",
doi = "10.1007/978-3-319-22177-9_19",
language = "English (US)",
isbn = "9783319221762",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "243--254",
editor = "Igor Walukiewicz and Adrian Kosowski",
booktitle = "Fundamentals of Computation Theory - 20th International Symposium, FCT 2015, Proceedings",
}