zbMATH — the first resource for mathematics

Graph minors. XIV: Extending an embedding. (English) Zbl 0840.05017
This paper is one of a series by the authors examining graph minors and the structure of graphs. It contains a lemma to be used in later papers, specifically towards describing the structure of graphs not containing a fixed graph as a minor. These graphs will be “tree-like” structures whose pieces are “almost” of low genus. The main question herein is: When can a drawing of a subgraph \(H\) in a surface be extended to a drawing of all of \(G\)? Several assumptions make this question easier: Let \(H\) be a subdivision of a 3-connected graph and suppose that every noncontractible curve in the surface intersects \(H\) in many points. This means that locally the graph has a unique planar embedding. The main result herein is: An embedding of such an \(H\) extends to one of a 4-connected \(G\) unless there exists one of two specific obstructions. The authors prove a similar result for 3-connected \(G\), but the statement is complicated by the fact some obstructions are separated from \(H\) by three vertices. They also prove a similar result for the sphere, but the statement is complicated by defining which side of a curve is the inside.

05C10 Planar graphs; geometric and topological aspects of graph theory
Full Text: DOI