Contraction checking in graphs on surfaces

DOI10.4230/LIPICS.STACS.2012.182MaRDI QIDQ2904760zbMATH OpenFDO

Authors Marcin Kamiński, Dimitrios M. Thilikos

Publication date 23 August 2012

Full work available at URL https://doi.org/10.4230/LIPICS.STACS.2012.182

zbMATH Keywords

surfaceslinkagesparameterized algorithmscontractionstopological minors

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Planar graphs; geometric and topological aspects of graph theory (05C10)

Recommendations

• Contractions of Planar Graphs in Polynomial Time
• Obtaining planarity by contracting few edges
• Obtaining planarity by contracting few edges
• Contracting planar graphs to contractions of triangulations
• MSOL restricted contractibility to planar graphs

Cited in

(7)

• Detecting fixed patterns in chordal graphs in polynomial time
• Graph minors and parameterized algorithm design
• Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable
• A more accurate view of the flat wall theorem
• Detecting induced minors in AT-free graphs
• Combing a Linkage in an Annulus
• Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm

This page was built for publication: Contraction checking in graphs on surfaces

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