  A geographic network is a graph whose vertices are restricted to lie in a
prescribed region in the plane. In this paper we begin to study the following
fundamental problem for geographic networks: can a given geographic network be
drawn without crossings? We focus on the seemingly simple setting where each
region is a vertical segment, and one wants to connect pairs of segments with a
path that lies inside the convex hull of the two segments. We prove that when
paths must be drawn as straight line segments, it is NP-complete to determine
if a crossing-free solution exists, even if all vertical segments have unit
length. In contrast, we show that when paths must be monotone curves, the
question can be answered in polynomial time. In the more general case of paths
that can have any shape, we show that the problem is polynomial under certain
assumptions.
