Adjacent Crossings Do Matter

Authors

  • Radoslav Fulek
  • Michael Pelsmajer
  • Marcus Schaefer
  • Daniel Štefankovič

DOI:

https://doi.org/10.7155/jgaa.00266

Keywords:

graph drawing , independent odd crossing number , crossing numbers , algebraic crossing number , monotone drawings

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 the two edges share no endpoint. For a graph G, let ocr(G) be the smallest number 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 an open question of Székely. The same graph G also separates two notions of algebraic crossing numbers that Tutte expected to be the same. The graph G was found via considering 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. In an ordered graph, the vertices have a left-to-right ordering that must be preserved in x-monotone drawings. For every integer n>0 we construct an ordered graph G such that for x-monotone drawings, the monotone variant of ocr and iocr satisfy 2=mon-iocr(G)<= mon-ocr(G)-n. We can also separate mon-ocr from its variant in which crossings of adjacent edges are prohibited. We also offer a general translation result from monotone separations to non-monotone separations. This could prove useful in settling several open separation problems, such as pair crossing number versus crossing number.

Downloads

Download data is not yet available.

Downloads

Published

2012-09-01

How to Cite

Fulek, R., Pelsmajer, M., Schaefer, M., & Štefankovič, D. (2012). Adjacent Crossings Do Matter. Journal of Graph Algorithms and Applications, 16(3), 759–782. https://doi.org/10.7155/jgaa.00266