Drawings Graphs on Two and Three Lines
Cornelsen, Sabine and Schank, Thomas and Wagner, Dorothea (2002) Drawings Graphs on Two and Three Lines. In: Graph Drawing 10th International Symposium, GD 2002, August 26-28, 2002, Irvine, CA, USA , pp. 31-41 (Official URL: http://dx.doi.org/10.1007/3-540-36151-0_4).
Full text not available from this repository.
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. This has previously been known only for trees. We utilize this result to obtain planar drawings on three lines for a generalization of bipartite graphs, also in linear time.
Repository Staff Only: item control page