TY - JOUR

T1 - Uniqueness of Highly Representative Surface Embeddings

AU - Seymour, P. D.

AU - Thomas, Robin

N1 - Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

PY - 1996/12

Y1 - 1996/12

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=1542475417&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=1542475417&partnerID=8YFLogxK

U2 - 10.1002/(SICI)1097-0118(199612)23:4<337::AID-JGT2>3.0.CO;2-S

DO - 10.1002/(SICI)1097-0118(199612)23:4<337::AID-JGT2>3.0.CO;2-S

M3 - Article

AN - SCOPUS:1542475417

SN - 0364-9024

VL - 23

SP - 337

EP - 349

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 4

ER -