Adjacent Crossings Do Matter
Radoslav Fulek, Michael J. Pelsmajer, Marcus Schaefer, Daniel Štefankovič · Journal of Graph Algorithms and Applications · 2012
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 they share no endpoint. For a graph G,letocr(G) be the smallest number of 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 a question by Székely, and—for the first time—giving evidence that crossings of adjacent edges may not always be trivial to eliminate. The graph G is based on a separation of iocr and ocr for 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. A graph is ordered if each of its vertices is assigned a distinct x-coordinate. We construct a family of ordered graphs such that for x-monotone drawings, the monotone variants of ocr and iocr satisfy mon-iocr(G)