Contractions of Planar Graphs in Polynomial Time

DOI10.1007/978-3-642-15775-2_11MaRDI QIDQ3586456zbMATH OpenOpenAlexFDO

Authors Marcin Kamiński, Daniël Paulusma, Dimitrios M. Thilikos

Publication date 6 September 2010

Published in Algorithms – ESA 2010 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-15775-2_11

zbMATH Keywords

contractiondual graphplanar graphtopological minor

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Contracting planar graphs to contractions of triangulations
• Contracting a planar graph efficiently
• The computational complexity of graph contractions I: Polynomially solvable and NP-complete cases
• The computational complexity of graph contractions II: Two tough polynomially solvable cases
• On planar perfectly contractile graphs
• scientific article; zbMATH DE number 4130432
• The complexity of graph contractions.
• Fast sub-exponential algorithms and compactness in planar graphs
• Contraction decomposition in unit disk graphs and algorithmic applications in parameterized complexity
• Algorithms for Perfectly Contractile Graphs

Cited in

(30)

• The isomorphism problem for classes of graphs closed under contraction
• On planar perfectly contractile graphs
• Approximation algorithms via contraction decomposition
• Obtaining planarity by contracting few edges
• Modulo orientations and matchings in graphs
• Detecting induced star-like minors in polynomial time
• Increasing the minimum degree of a graph by contractions
• Contraction checking in graphs on surfaces
• Obtaining planarity by contracting few edges
• Minimal disconnected cuts in planar graphs
• Edge contractions in subclasses of chordal graphs
• Increasing the minimum degree of a graph by contractions
• Edge contractions in subclasses of chordal graphs
• scientific article; zbMATH DE number 2079739 (Why is no real title available?)
• scientific article; zbMATH DE number 1792612 (Why is no real title available?)
• MSOL restricted contractibility to planar graphs
• scientific article; zbMATH DE number 6438523 (Why is no real title available?)
• MSOL restricted contractibility to planar graphs
• scientific article; zbMATH DE number 4183439 (Why is no real title available?)
• Contracting chordal graphs and bipartite graphs to paths and trees
• Contracting bipartite graphs to paths and cycles
• Contracting bipartite graphs to paths and cycles
• Contracting chordal graphs and bipartite graphs to paths and trees
• The complexity of contracting bipartite graphs into small cycles
• Contracting planar graphs to contractions of triangulations
• Finding maximum common contractions between phylogenetic networks
• Revisiting path contraction and cycle contraction
• The complexity of contracting bipartite graphs into small cycles
• The parameterized landscape of labeled graph contractions
• Containment relations in split graphs

This page was built for publication: Contractions of Planar Graphs in Polynomial Time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3586456)