A graph is upward planar if it can be drawn without edge crossings such that all edges point upward. Upward planar graphs have been studied on the plane, the standing and rolling cylinders. For all these surfaces, the respective decision problem NP-hard in general. Efficient testing algorithms exist if the graph contains a single source and a single sink but only for the plane and standing cylinder. Here we show that there is a linear-time algorithm to test whether a strongly connected graph is upward planar on the rolling cylinder. For our algorithm, we introduce dual and directed SPQR-trees as extensions of SPQR-trees.
展开▼
