Contractions of Planar Graphs in Polynomial Time

DOI10.1007/978-3-642-15775-2_11zbMath1287.05151OpenAlexW1584371244MaRDI QIDQ3586456

Dimitrios M. Thilikos, Marcin Kaminski, Daniël Paulusma

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

contractionplanar graphdual graphtopological minor

Mathematics Subject Classification ID

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

Related Items (14)

Increasing the Minimum Degree of a Graph by Contractions ⋮ Modulo orientations and matchings in graphs ⋮ Detecting induced star-like minors in polynomial time ⋮ Increasing the minimum degree of a graph by contractions ⋮ Minimal Disconnected Cuts in Planar Graphs ⋮ The complexity of contracting bipartite graphs into small cycles ⋮ Edge contractions in subclasses of chordal graphs ⋮ Contracting planar graphs to contractions of triangulations ⋮ Edge Contractions in Subclasses of Chordal Graphs ⋮ 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 ⋮ Containment relations in split graphs

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