Graph minors. IX. Disjoint crossed paths

Neil Robertson, P. D. Seymour

Research output: Contribution to journalArticlepeer-review

75 Scopus citations

Abstract

Let G be a graph, with a cyclic order imposed on a subset of its vertices (called "special" vertices). We show that either 1. (i) modulo (≤3)-separations, G can be drawn in a disc with no crossings except in one "small" area, and with its special vertices on the outside in the correct order, or 2. (ii) there is a partition of the special vertices into two "semicircles," and there is a large collection of vertex-disjoint paths of G running from one semicircle to the other, such that each of these paths is either crossed by another or lies between two others. This is basically a lemma to be used in later papers.

Original languageEnglish (US)
Pages (from-to)40-77
Number of pages38
JournalJournal of Combinatorial Theory, Series B
Volume49
Issue number1
DOIs
StatePublished - Jun 1990
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. IX. Disjoint crossed paths'. Together they form a unique fingerprint.

Cite this