Computer Science – Discrete Mathematics
Scientific paper
2012-04-13
Computer Science
Discrete Mathematics
45 pages, 18 figures
Scientific paper
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.
Jelínek Vit
Kratochvil Jan
Rutter Ignaz
No associations
LandOfFree
A Kuratowski-Type Theorem for Planarity of Partially Embedded Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Kuratowski-Type Theorem for Planarity of Partially Embedded Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Kuratowski-Type Theorem for Planarity of Partially Embedded Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-143695