Home  Issues  Aims and Scope  Instructions for Authors 
Special Issue on Selected Papers from the Nineteenth International Symposium on Graph Drawing, GD 2011
DOI: 10.7155/jgaa.00266
Adjacent Crossings Do Matter
Radoslav Fulek,
Michael J. Pelsmajer,
Marcus Schaefer, and
Daniel Štefankovič
Vol. 16, no. 3, pp. 759782, 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 xmonotone 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 lefttoright ordering that must be preserved in xmonotone drawings. For every integer n>0 we construct an ordered graph G such that for xmonotone
drawings, the monotone variant of ocr and iocr satisfy 2=moniocr(G)<= monocr(G)n. We can also
separate monocr from its variant in which crossings of adjacent edges are prohibited.
We also offer a general translation result from monotone separations to nonmonotone 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.
