Special Issue on Selected Papers from the Nineteenth International Symposium on Graph Drawing, GD 2011
Adjacent Crossings Do Matter
Radoslav Fulek, Michael J. Pelsmajer, Marcus Schaefer, and Daniel Štefankovič
Vol. 16, no. 3, pp. 759-782, 2012. Regular paper.
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.
Submitted: November 2011.
Reviewed: February 2012.
Revised: February 2012.
Accepted: April 2012.
Final: April 2012.
Published: September 2012.
article (PDF)