A Kuratowski-type theorem for planarity of partially embedded graphs

作者：Jelinek Vit; Kratochvil Jan; Rutter Ignaz^*

来源：Computational Geometry-Theory and Applications, 2013, 46(4): 466-492.

DOI：10.1016/j.comgeo.2012.07.005

• Planar graphs
• Partially embedded graphs
• Kuratowski theorem

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 graph G has a planar embedding that extends the embedding H. %26lt;br%26gt;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. %26lt;br%26gt;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.

• 出版日期2013-5