  In this paper, we consider the following graph embedding problem: Given a
bipartite graph G = (V1; V2;E), where the maximum degree of vertices in V2 is
4, can G be embedded on a two dimensional grid such that each vertex in V1 is
drawn as a line segment along a grid line, each vertex in V2 is drawn as a
point at a grid point, and each edge e = (u; v) for some u 2 V1 and v 2 V2 is
drawn as a line segment connecting u and v, perpendicular to the line segment
for u? We show that this problem is NP-complete, and sketch how our proof
techniques can be used to show the hardness of several other related problems.
