Search Results

A typical question in graph drawing is to determine, for a given graph drawing style, the boundary between polynomial-time solvability and NP-hardness. For two examples from the area of drawing graphs with few slopes, we sharpen this boundary. We suggest a framework for a certain type of NP-hardness constructions where graphs have some parts that can only be realized as rigid structures, whereas other parts allow a controllable degree of flexibility. Starting with an NP-complete problem involving planarity (here, we use planar monotone rectilinear 3-SAT), we consider first a reduction to a planar graph, which can be adjusted to an outerplanar graph, and finally to an outerpath. An outerplanar graph is a graph admitting an outerplanar drawing, that is, a crossing-free drawing where every vertex lies on the outer face, and an outerpath is a graph admitting an outerplanar drawing where the weak dual is a path. The (weak) dual of a graph drawing is the graph that has a node for every (inner) face and a link if two faces share an edge. Specifically, we first show that, for every upward-planar directed outerpath G, it is NP-hard to decide whether G admits an upward-planar straight-line drawing where every edge has one of three distinct slopes, and we second show that, for every undirected outerpath G, it is NP-hard to decide whether G admits a proper level-planar straight-line drawing where every edge has one of two distinct slopes. For both problems, NP-hardness has been known before for outerplanar graphs.