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 , 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.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-36151-0_4
Classifications: G Algorithms and Complexity > G.770 Planarity Testing
URI: http://gdea.informatik.uni-koeln.de/id/eprint/206

Actions (login required)

View Item View Item