Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
|
DOI: 10.7155/jgaa.00087 Drawing Graphs on Two and Three Lines Sabine Cornelsen , Thomas Schank , and Dorothea Wagner 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 |
| Journal of Graph Algorithms and Applications |