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

zbMATH Keywords

connectivityplanar graphvertex cut

Mathematics Subject Classification ID

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