A Kuratowski-type theorem for planarity of partially embedded graphs

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. We introduce a containment relation of Pegs analogous to graph m...

Full description

Saved in:
Bibliographic Details
Published in:Computational geometry : theory and applications 2013-05, Vol.46 (4), p.466-492
Main Authors: Jelínek, Vít, Kratochvíl, Jan, Rutter, Ignaz
Format: Article
Language:English
Subjects:
Algorithms
Computational geometry
Containment
Graphs
Kuratowski theorem
Mathematical analysis
Obstructions
Partially embedded graphs
Planar graphs
Recognition
Theorems
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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. 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.
ISSN:0925-7721
DOI:10.1016/j.comgeo.2012.07.005