MSOL restricted contractibility to planar graphs

DOI10.1016/j.tcs.2017.02.030zbMath1370.68113OpenAlexW2594929095WikidataQ62048074 ScholiaQ62048074MaRDI QIDQ527397

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

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

contractionplanar graphFPT algorithmMSOL formula

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On graph contractions and induced minors
• Some simplified NP-complete graph problems
• The complexity of induced minors and related problems
• A simpler proof of the excluded minor theorem for higher surfaces
• Graph minors. XIII: The disjoint paths problem
• Obtaining planarity by contracting few edges
• Crossing Number is NP-Complete
• Obtaining a Planar Graph by Vertex Deletion
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• Efficient Planarity Testing
• MSOL Restricted Contractibility to Planar Graphs
• Computing crossing numbers in quadratic time
• AN IMPROVED ALGORITHM FOR FINDING TREE DECOMPOSITIONS OF SMALL WIDTH
• Obtaining a Bipartite Graph by Contracting Few Edges
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth