Graph minors. XII: Distance on a surface
type: Item
instance of: scholarly article
title: Graph minors. XII: Distance on a surface
zbMATH Open document ID: 0840.05016
author: Neil Robertson
author: Paul Seymour
published in: Journal of Combinatorial Theory. Series B
publication date: 1996-07-04T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 798749
zbMATH Keywords: distance on a surface
zbMATH Keywords: graph minors
zbMATH Keywords: structure of graphs
zbMATH Keywords: nonspherical surface
zbMATH Keywords: representativity
zbMATH Keywords: noncontractible curve
zbMATH Keywords: metric on a surface
zbMATH Keywords: embedding
zbMATH Keywords: tangles
reviewed by: Dan S. Archdeacon
MaRDI profile type: Publication
full work available at URL: jctb.1995.1034
OpenAlex ID: W2028037658
DOI: 10.1006/JCTB.1995.1034
Recommended article: Graph minors. XI: Circuits on a surface
Recommended article: Graph minors and graphs on surfaces
Recommended article: Graph minors. VII: Disjoint paths on a surface
Recommended article: Q3684139
Recommended article: Graph minors. VIII: A Kuratowski theorem for general surfaces
Recommended article: Minimal graphs with respect to geometric distance realizability
Recommended article: Graph minors and minimum degree
Recommended article: Graph minors. XIII: The disjoint paths problem
Recommended article: On the minimum distance in a \(k\)-vertex set in a graph
Recommended article: Graph minors. XIX: Well-quasi-ordering on a surface.
description: scientific article; zbMATH DE number 798749