K-Spine, 1-Bend Planarity

In this paper, we study k-spine, h-bend planar drawings in which each vertex of a planar graph G lies on one of k $\geq$ 1 horizontal lines and each edge of G is drawn as a polyline containing at most h $\geq$ 0 bends. A graph with a k-spine, h-bend planar drawing is said to be k-spine, h-bend planar. We mainly focus on k-spine, 1-bend planar drawings, showing that for each k $\geq$ 2, there exists a planar graph that is not k-spine, 1-bend planar, and furthermore, that it is NP-hard to test k-spine, 1-bend planarity. Given this complexity result, we further narrow our focus onto 2-spine, 1-bend planar drawings. We characterize 2-spine, 1-bend planarity using a new generalization of Hamiltonian graphs that we call Hamiltonian-with-handles graphs. We observe that our characterization naturally extends the connection between 2-page book embeddings and Hamiltonicity. Finally, we use our characterization to show that 2-outerplanar graphs are 2-spine, 1-bend planar.