Minimal Disconnected Cuts in Planar Graphs
DOI10.1007/978-3-319-22177-9_19zbMath1434.68361OpenAlexW1604319589MaRDI QIDQ2947884
Daniël Paulusma, Dimitrios M. Thilikos, Marcin Kaminski, Anthony Stewart
Publication date: 29 September 2015
Published in: Fundamentals of Computation Theory (Search for Journal in Brave)
Full work available at URL: http://dro.dur.ac.uk/16142/1/16142.pdf
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph minors (05C83) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Connectivity (05C40)
Cites Work
- Unnamed Item
- Unnamed Item
- Parameterizing cut sets in a graph by the number of their components
- On stable cutsets in claw-free graphs and planar graphs
- Decomposition by clique separators
- An algorithm for finding clique cut-sets
- On stable cutsets in graphs
- The computational complexity of disconnected cut and \(2 K_2\)-partition
- On disconnected cuts and separators
- Finding small separators in linear time via treewidth reduction
- Recognizing decomposable graphs
- The Complexity of the List Partition Problem for Graphs
- Contractions of Planar Graphs in Polynomial Time
- The complexity of the matching-cut problem for planar graphs and other graph classes
- A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
- Reducibility among Combinatorial Problems
- Fast Skew Partition Recognition
- Finding topological subgraphs is fixed-parameter tractable
This page was built for publication: Minimal Disconnected Cuts in Planar Graphs
