Trading crossings for handles and crosscaps

✍ Scribed by Dan Archdeacon; C. Paul Bonnington; Jozef Širáň

• Book ID: 102341509
• Publisher: John Wiley and Sons
• Year: 2001
• Tongue: English
• Weight: 180 KB
• Volume: 38
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.10009

✦ Synopsis

Let c k cr k (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 c 0 ,c 1 ,c 2 ,F F F encodes the trade-off between adding handles and decreasing crossings. We focus on sequences of the type c 0 b c 1 b c 2 0; equivalently, we study the planar and toroidal crossing number of doubly-toroidal graphs. For every 4 b 0 we construct graphs whose orientable crossing sequence satis®es c 1 /c 0 b 5/6 À 4. In other words, we construct graphs where the addition of one handle can save ÐÐÐÐÐÐÐÐÐÐÐÐÐÐÐÐÐÐ