Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
The paper in this page has been just accepted in JGAA and is in the queue for being assigned a volume and an issue number. It has been accepted by one of the JGAA editors and its content will no longer be modified. However, the publication format of the paper may still be subject to minor changes.
|
DOI: 10.7155/jgaa.00266 Adjacent Crossings Do Matter Radoslav Fulek , Michael J. Pelsmajer , Marcus Schaefer , and Daniel Štefankovič To be published in the Special Issue of GD 2011. Abstract In a drawing of a graph, two edges form an odd pair if they cross each other an odd number of times. A pair of edges is independent if the two edges share no endpoint. For a graph G, let ocr(G) be the smallest number odd pairs in a drawing of G and let iocr(G) be the smallest number of independent odd pairs in a drawing of G. We construct a graph G with iocr(G)<ocr(G), answering an open question of Székely. The same graph G also separates two notions of algebraic crossing numbers that Tutte expected to be the same. The graph G was found via considering monotone drawings of ordered graphs. A drawing of a graph is x-monotone if every edge intersects every vertical line at most once and every vertical line contains at most one vertex. In an ordered graph, the vertices have a left-to-right ordering that must be preserved in x-monotone drawings. For every integer n>0 we construct an ordered graph G such that for x-monotone drawings, the monotone variant of ocr and iocr satisfy 2=mon-iocr(G)<= mon-ocr(G)-n$. We can also separate mon-ocr from its variant in which crossings of adjacent edges are prohibited. We also offer a general translation result from monotone separations to non-monotone separations. This could prove useful in settling several open separation problems, such as pair crossing number versus crossing number.
|
Posted here: May 2012. |
| Journal of Graph Algorithms and Applications |