Adding and Deleting Crossings in Drawings of Graphs

J.E. Cottingham1, R.D. Ringeisen2
1IQ Interactive P.O, Box 147 Clemson, SC 29633-0147
2Office of the Vice Chancellor for Academic Affairs East Carolina University Greenville, NC 27858-4353

Abstract

Given a good drawing of a graph on some orientable surface, there exists a good drawing of the same graph with one more or one less crossing on an orientable surface which can be exactly determined. Our methods use a new combinatorial representation for drawings. These results lead to bounds related to the Thrackle Conjecture.