How to make a bad pseudoline arrangement worse

The image below is a drawing of (part of) a pseudoline arrangement, a collection of curves in the plane that behave like lines in the sense that each curve partitions the plane into two unbounded regions and each two curves have exactly one point of intersection, where they cross. It's from my latest arXiv preprint, "Convex-Arc Drawings of Pseudolines" (with Mereke van Garderen, Bettina Speckmann, and Torsten Ueckerdt, arXiv:1601.06865).

The repeated yellow squares within the image are themselves smaller pseudoline arrangements, all the same as each other, with nine pseudolines each. I drew them more curvy than they need to be, but the special property of these arrangements is that they need to be at least a little bit curvy: they cannot be drawn with straight lines.

The point of this image is that it repeats! The black parts outside the yellow squares show how to connect up the pseudolines so that the repetition still obeys the requirements of a pseudoline arrangement. The nine pseudolines in any one square must never go to the same square as each other again (otherwise they would cross twice, not allowed). To prevent this, one of the nine pseudolines in each square (the one that comes in the top and goes out the bottom) connects horizontally to the next square across, another connects one square down on the left and one square up on the right, another connects two squares down and up, etc. In this way, an \( n \) by \( n \) grid of yellow squares can be glued together using a total of only \( O(n) \) pseudolines. They won't all cross each other within the grid, but that can be fixed up by adding extra crossings outside the grid.

If you start with a small constant-sized pseudoline arrangement requiring at least one bend, then after performing this expansion you get a big pseudoline arrangement requiring a quadratic number of bends. Here I define a bend to be a vertex of a polygonal chain, but the same construction generalizes to show that if you draw the pseudolines as smooth spline curves you need a quadratic number of knots, or if you draw them as piecewise-circular curves you need a quadratic number of arcs. It's not hard to draw any pseudoline arrangement with only this many bends (just use a wiring diagram) but one of the results of the paper is that you can still draw the arrangement with quadratically many bends even if you require all of the pseudolines to be convex curves.

Another part of the paper concerns "weak pseudoline arrangements", where not every pair of curves is required to cross (but they can still only intersect in a single crossing point). We say that a weak pseudoline arrangement is outerplanar if every crossing point belongs to an unbounded face. Outerplanar arrangements can't always be straightened in the plane; for instance rotating the parabola \( y=x^2+1 \) by right angles around the origin forms a pseudoline arrangement with four pseudolines that cannot be made straight. However, we show that this is a special property of the Euclidean plane: in the hyperbolic plane, every outerplanar arrangement can be straightened. This leads to Euclidean drawings with only two bends per pseudoline, but maybe only one bend is possible, I'm not sure.

Comments:

(More comments on G+)