Name
Abstract | ||
|---|---|---|
Let ck = crk (G) denote theminimum number of edge crossings when a graph G is drawn onan orientable surface of genus k. The (orientable) crossingsequence co,c1,c2…encodes thetrade-off between adding handles and decreasing crossings. We focuson sequences of the type co c1 c2 = 0; equivalently,we study the planar and toroidal crossing number of doubly-toroidalgraphs. For every ε 0 we construct graphs whoseorientable crossing sequence satisfiesc1-co 5-6-ε. Inother words, we construct graphs where the addition of one handlecan save roughly 1-6th of the crossings, but the addition of asecond handle can save five times more crossings. We similarlydefine the non-orientable crossing sequence~0,~1,~2, … for drawings onnon-orientable surfaces. We show that for every ~0~1 0 there exists a graph with non-orientablecrossing sequence ~0, ~1, 0. We conjecturethat every strictly-decreasing sequence of non-negative integerscan be both an orientable crossing sequence and a non-orientablecrossing sequence (with different graphs). © 2001 John Wiley& Sons, Inc. J Graph Theory 38: 230243, 2001 |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1002/jgt.v38:4 | Journal of Graph Theory |
Keywords | Field | DocType |
non-orientablecrossing sequence,crossingsequence co,type co c1 c2,sequence satisfiesc1-co,different graph,graph g,trading crossing,denote theminimum number,onan orientable surface,edge crossing,strictly-decreasing sequence,crossing number | Graph theory,Integer,Discrete mathematics,Graph,Combinatorics,Crossing sequence,Crossing number (graph theory),1-planar graph,Conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
38 | 4 | 0364-9024 |
Citations | PageRank | References |
3 | 0.59 | 8 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dan Archdeacon | 1 | 277 | 50.72 |
| C. Paul Bonnington | 2 | 100 | 19.95 |
| Jozef Širáň | 3 | 362 | 54.24 |