The Open UniversitySkip to content
 

Trading crossings for handles and crosscaps

Archdeacon, D.; Bonnington, P. and Siran, J. (2001). Trading crossings for handles and crosscaps. Journal of Graph Theory, 38(4) pp. 230–243.

DOI (Digital Object Identifier) Link: http://dx.doi.org/10.1002/jgt.10009
Google Scholar: Look up in Google Scholar

Abstract

Let ck = crk (G) denote the minimum number of edge crossings when a graph G is drawn on an orientable surface of genus k. The (orientable) crossing sequence co, c1,c2encodes the trade-off between adding handles and decreasing crossings. We focus on sequences of the type co > c1 > c2 = 0; equivalently, we study the planar and toroidal crossing number of doubly-toroidal graphs. For every > 0 we construct graphs whose orientable crossing sequence satisfies c1/co > 5/6-. In other words, we construct graphs where the addition of one handle can save roughly 1/6th of the crossings, but the addition of a second handle can save five times more crossings. We similarly define the non-orientable crossing sequence 0,1,2, ··· for drawings on non-orientable surfaces. We show that for every 0 > 1 > 0 there exists a graph with non-orientable crossing sequence 0, 1, 0. We conjecture that every strictly-decreasing sequence of non-negative integers can be both an orientable crossing sequence and a non-orientable crossing sequence (with different graphs).

Item Type: Journal Article
ISSN: 0364-9024
Keywords: graph embeddings; crossing number
Academic Unit/Department: Mathematics, Computing and Technology > Mathematics and Statistics
Item ID: 8099
Depositing User: Jozef Širáň
Date Deposited: 14 Jun 2007
Last Modified: 02 Dec 2010 20:00
URI: http://oro.open.ac.uk/id/eprint/8099
Share this page:

Actions (login may be required)

View Item
Report issue / request change

Policies | Disclaimer

© The Open University   + 44 (0)870 333 4340   general-enquiries@open.ac.uk