A Kuratowski-type theorem for planarity of partially embedded graphs ?
A partially embedded graph (or Peg) is a triple (G,H,H) ( G , H , H ) , where G is a graph, H is a subgraph of G , and H H is a planar embedding of H. We say that a Peg(G,H,H) ( G , H , H ) is planar if the graph G  has a planar embedding that extends the embedding H H . We introduce a containment relation of Pegs analogous to graph minor containment, and characterize the minimal non-planar Pegs with respect to this relation. We show that all the minimal non-planar Pegs except for finitely many belong to a single easily recognizable and explicitly described infinite family. We also describe a more complicated containment relation which only has a finite number of minimal non-planar Pegs. Furthermore, by extending an existing planarity test for Pegs, we obtain a polynomial-time algorithm which, for a given Peg, either produces a planar embedding or identifies an obstruction.
partially embedded graphs planar graphs kuratowski theorem