Trading crossings for handles and crosscaps |
| |
Authors: | Dan Archdeacon C Paul Bonnington Jozef ir |
| |
Institution: | Dan Archdeacon,C. Paul Bonnington,Jozef ?iráň |
| |
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,c2…encodes 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). © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 230–243, 2001 |
| |
Keywords: | graph embeddings crossing number |
|
|