# Speaker: Michael Bannister

##
Complexity of Finding Non-Planar Rectilinear Drawings of Graphs

##
by Manuch, Patterson, Poon and Thachuk

We study the complexity of the problem of finding non-planar rectilinear
drawings of graphs. This problem is known to be NP-complete. We consider
natural restrictions of this problem where constraints are placed on the
possible orientations of edges. In particular, we show that if each edge
has prescribed direction "left", "right", "down" or "up", the problem of
finding a rectilinear drawing is polynomial, while finding such a drawing
with the minimum area is NP-complete. When assigned directions are
"horizontal" or "vertical" or a cyclic order of the edges at each vertex
is specified, the problem is NP-complete. We show that these two
NP-complete cases are fixed parameter tractable in the number of vertices
of degree 3 or 4.