Stretchability of pseudolines is NP-hard. (English) Zbl 0751.05023

Shor, Peter W.

Applied geometry and discrete mathematics, Festschr. 65th Birthday Victor Klee, DIMACS, Ser. Discret. Math. Theor. Comput. Sci. 4, 531-554 (1991).

[For the entire collection see Zbl 0726.00015.]
A pseudoline arrangement is a partition of the plane by a set of pseudolines, or topological lines, such that any two pseudolines intersect in at most one point and then also cross in that point. A pseudoline arrangement is stretchable if the same combinatorial structure can be realized by a line arrangement. The author shows that the problem of finding a realization of a given pseudoline arrangement by a line arrangement is NP-hard. He also constructs a symmetric pseudoline arrangement that cannot be realized by symmetric line arrangement, but is stretchable.
The NP-hardness also follows from the work of N. E. Mnëv [Topology and geometry, Rohlin Semin. 1984-1986, Lect. Notes Math. 1346, 527-543 (1988; Zbl 0667.52006)], and, at the end of this paper, the author gives a short discussion of that work viewed from a complexity theory point of view.

Reviewer: H.Cuypers (Eindhoven)

MSC:

05B35	Combinatorial aspects of matroids and geometric lattices
52C99	Discrete geometry

Keywords:

pseudoline arrangement; NP-hardness