Drawing Graphs on Two and Three Lines
Sabine Cornelsen, Thomas Schank, Dorothea Wagner · Journal of Graph Algorithms and Applications · 2004
We give a linear-time algorithm to decide whether a graph has a planar LL-drawing, i.e., a planar drawing on two parallel lines. We utilize this result to obtain planar drawings on three lines for a generalization of bipartite graphs, also in linear time.