Drawing Graphs on Two and Three Lines
Vol. 8, no. 2, pp. 161-177, 2004. Regular paper.
Abstract 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.
Submitted: March 2003.
Revised: January 2004.
Communicated by Xin He
article (PDF)