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 language | English (US) |
---|---|
Pages (from-to) | 40-77 |
Number of pages | 38 |
Journal | Journal of Combinatorial Theory, Series B |
Volume | 49 |
Issue number | 1 |
DOIs | |
State | Published - Jun 1990 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics