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.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics