Adjacent Crossings Do Matter

Fulek, Radoslav and Pelsmajer, Michael J. and Schaefer, Marcus and Štefankovič, Daniel (2012) Adjacent Crossings Do Matter. In: Graph Drawing 19th International Symposium, GD 2011, September 21-23, 2011 , pp. 343-354(Official URL:

Full text not available from this repository.


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, let ocr(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) < O(mon-ocr(G)1/2 ).

Item Type: Conference Paper
Additional Information: 10.1007/978-3-642-25878-7_33
Classifications: G Algorithms and Complexity > G.420 Crossings

Actions (login required)

View Item View Item