Contracting planar graphs to contractions of triangulations

Marcin Kaminski, Daniel Paulusma, Dimitrios M. Thilikos

For every graph $H$, there exists a polynomial-time algorithm deciding if a planar input graph $G$ can be contracted to~$H$. However, the degree of the polynomial depends on the si…