Stretchability of pseudolines is NP-hard.

*(English)*Zbl 0751.05023
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.

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)