Planarity has been successfully exploited to design faster and more accurate approximation algorithms for many graph optimization problems. The celebrated theorem of Kuratowski completely characterizes planar graphs as those excluding K_5 and K_{3,3} as minors. Kuratowski's theorem allows one to generalize planar graphs to H-minor-free graphs: those that exclude a...