zbMATH — the first resource for mathematics

Graph minors. XII: Distance on a surface. (English) Zbl 0840.05016
This paper is one of a series by the authors examining graph minors and the structure of graphs. It contains lemmas to be used in later papers, specifically towards describing the structure of graphs not containing a fixed graph as a minor. A graph embedded on a nonspherical surface has representativity \(\theta\) if every noncontractible curve in the surface intersects the graph in at least \(\theta\) points. An embedded graph can be used to define a metric on a surface (see XI in this series; ibid., Ser. B 60, No. 1, 72-106 (1994; Zbl 0799.05016)). The purpose of this paper is to make local changes in the embedding or the surface and examine the effect on the representativity and on the derived metric. The technique involves tangles (see X in this series; ibid., Ser. B 52, No. 2, 153-190 (1991; Zbl 0764.05069)) which are related to small vertex cuts in the graph.

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