Contractions of graphs on surfaces in polynomial time
Marcin Kami, Daniël Paulusma, Dimitrios M. Thilikos · 2010
We prove that for every integer g 0 and graph H, there exists a polynomial-time algorithm deciding whether an input graph of Euler genus at most g can be contracted to H. We introduce surface contractions and surface topological minors of embedded graphs. We prove that an embedded graph H is a surface contraction of an embedded graph G if and only if the geometric dual of H is a surface topological minor of the geometric dual of G.