  Given $n$ line segments in the plane, do they form the edge set of a
\emph{weakly simple polygon}; that is, can the segment endpoints be perturbed
by at most $\varepsilon$, for any $\varepsilon>0$, to obtain a simple polygon?
While the analogous question for \emph{simple polygons} can easily be answered
in $O(n\log n)$ time, we show that it is NP-complete for weakly simple
polygons. We give $O(n)$-time algorithms in two special cases: when all
segments are collinear, or the segment endpoints are in general position. These
results extend to the variant in which the segments are \emph{directed}, and
the counterclockwise traversal of a polygon should follow the orientation.
  We study related problems for the case that the union of the $n$ input
segments is connected. (i) If each segment can be subdivided into several
segments, find the minimum number of subdivision points to form a weakly simple
polygon. (ii) If new line segments can be added, find the minimum total length
of new segments that creates a weakly simple polygon. We give worst-case upper
and lower bounds for both problems.
