A Kuratowski-Type Theorem for Planarity of Partially Embedded Graphs

Vít Jelínek, Jan Kratochvíl, Ignaz Rutter

A partially embedded graph (or PEG) is a triple (G,H,\H), where G is a graph, H is a subgraph of G, and \H is a planar embedding of H. We say that a PEG (G,H,\H) is planar if the g…