## 3 March 2000:

Weaving Patterns of Lines and Line Segments in Space

Javid Hüseynov, ICS, UC Irvine

A weaving W is a simple arrangement of lines (or line segments)
in the plane together with a binary relation specifying which line
is "above" the other. Two weavings are equivalent if the underlying
arrangements of lines are combinatorially equivalent and the
"above-below" relations are the same. An equivalence class of
weavings is called a weaving pattern.

In a perfect weaving pattern, along each line l of W, the lines
intersecting it are alternately "above" and "below". This paper
discusses the realization of weavings and weaving patterns in
3-space. The authors prove that:

- A perfect weaving pattern of n lines is realizable iff
n<=3
- A perfect m by n (bipartite) weaving pattern of line segments
is realizable iff min(m,n) <= 3
- If n -> infinity, then almost all weaving patterns are
nonrealizable.

(Based on a paper by János Pach, Richard Pollack, and Emo
Welzl, in *Algorithmica* 9:561-571, 1993.)