Graph Minors .XII. Distance on a Surface

Neil Robertson, Paul Douglas Seymour

Research output: Contribution to journalArticle

36 Scopus citations

Abstract

Let Γ a graph drawn on a connected surface ∑ which is not a sphere. It is “θ-representative” if every non-null-homotopic closed curve meets Γ at least θ times. Also, Γ defines a metric on ∑, discussed in an earlier paper. Our objective here is to study the effect on the metric and on the “representativeness” of making local changes in the drawing or in the surface. We also reformulate more compactly the main theorem of an earlier paper in terms of this metric. These are lemmas to be used later.

Original languageEnglish (US)
Pages (from-to)240-272
Number of pages33
JournalJournal of Combinatorial Theory, Series B
Volume64
Issue number2
DOIs
StatePublished - Jan 1 1995
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Graph Minors .XII. Distance on a Surface'. Together they form a unique fingerprint.

  • Cite this