Adjacent Crossings Do Matter
Radoslav, Fulek 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, Eindhoven, The Netherlands , pp. 343-354 (Official URL: http://dx.doi.org/10.1007/978-3-642-25878-7_33).
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 ).
Repository Staff Only: item control page