Adjacent Crossings Do MatterFulek, 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 2123, 2011 , pp. 343354(Official URL: http://dx.doi.org/10.1007/9783642258787_33). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783642258787_33
AbstractIn 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 xmonotone 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 xcoordinate. We construct a family of ordered graphs such that for xmonotone drawings, the monotone variants of ocr and iocr satisfy moniocr(G) < O(monocr(G)1/2 ).
Actions (login required)
