Adjacent Crossings Do Matter

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 Szekely, 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)).


Published in:
Proc. 19th International Symposium on Graph Drawing
Presented at:
19th International Symposium on Graph Drawing
Year:
2011
Publisher:
Berlin, Springer-Verlag Berlin
ISBN:
978-3-642-25877-0
Laboratories:




 Record created 2011-12-19, last modified 2018-03-17


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)