Let Σ be a (connected) surface of "complexity" κ; that is, Σ may be obtained from a sphere by adding either 1/2κ handles or κ crosscaps. Let ρ ≥ 0 be an integer, and let Γ be a "ρ-representative drawing" in Σ; that is, a drawing of a graph in Σ so that every simple closed curve in Σ that meets the drawing in <ρ points bounds a disc in Σ. Now let Γ′ be another drawing, in another surface Σ′ of complexity κ′, so that Γ and Γ′ are isomorphic as abstract graphs. We prove that (i) If ρ ≥ 100 log κ/ log log κ (or ρ ≥ 100 if κ ≤ 2) then κ′ ≤ κ, and if κ′ = κ and Γ is simple and 3-connected there is a homeomorphism from Σ to Σ′ taking Γ to Γ′, (ii) if Γ is simple and 3-connected and Γ′ is 3-representative, and ρ ≥ (320, 5 log κ), then either there is a homeomorphism from Σ to Σ′ taking Γ to Γ′, or κ′ ≥ κ + 10-4 ρ2.
|Original language||English (US)|
|Number of pages||13|
|Journal||Journal of Graph Theory|
|State||Published - Dec 1996|
All Science Journal Classification (ASJC) codes
- Geometry and Topology