MSOL restricted contractibility to planar graphs

DOI10.1016/J.TCS.2017.02.030MaRDI QIDQ527397zbMATHOpenAlexWikidataFDO

Authors James Abello, Pavel Klavík, Jan Kratochvíl, Tomáš Vyskočil

Publication date 11 May 2017

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2017.02.030

zbMATH Keywords

contractionFPT algorithmplanar graphMSOL formula

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) 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 representations (geometric and intersection representations, etc.) (05C62)

Recommendations

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

Cites work

• scientific article; zbMATH DE number 5485473 (Why is no real title available?)
• scientific article; zbMATH DE number 881174 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A simpler proof of the excluded minor theorem for higher surfaces
• An improved algorithm for finding tree decompositions of small width
• Computing crossing numbers in quadratic time
• Crossing Number is NP-Complete
• Efficient Planarity Testing
• Graph minors. XIII: The disjoint paths problem
• Graphs on surfaces
• MSOL restricted contractibility to planar graphs
• Obtaining a Planar Graph by Vertex Deletion
• Obtaining a bipartite graph by contracting few edges
• Obtaining planarity by contracting few edges
• On graph contractions and induced minors
• Some simplified NP-complete graph problems
• The complexity of induced minors and related problems
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues

Cited in

(3)

• Obtaining planarity by contracting few edges
• MSOL restricted contractibility to planar graphs
• Obtaining planarity by contracting few edges

This page was built for publication: MSOL restricted contractibility to planar graphs

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