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.

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. 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
ID Code:206

Repository Staff Only: item control page

References

T.C. Biedl. Drawing planar partitions I: LL-drawings and LH-drawings. In Proceedings of the 14th Annual ACM Symposium on Computational Geometry (SCG '98), pages 287-296, 1998.

T.C. Biedl, M. Kaufmann, and P. Mutzel. Drawing planar partitions II: HH-drawings. In J. Hromkovic, editor, Graph Theoretic Concepts in Computer Science, 24th International Workshop, (WG '98), volume 1517 of Lecture Notes in Computer Science, pages 124-136. Springer, 1998.

P. Eades, B.D. McKay, and N.C. Wormald. On an edge crossing problem. In Proceedings of the 9th Australian Computer Science Conference (ACSC 9), pages 327-334, 1986.

S. Felsner, G. Liotta, and S.K. Wismath. Straight-line drawings on restricted integer grids in two and three dimensions. In M. Jünger and P. Mutzel, editors, Proceedings of the 9th International Symposium on Graph Drawing (GD 2001), volume 2265 of Lecture Notes in Computer Science, pages 328-342. Springer, 2002.

U. Fößmeier and M. Kaufmann. Nice drawings for planar bipartite graphs. In G. Bongiovanni, D.P. Bovet, and G. Di Battista, editors, Proceedings of the 3rd Italian Conference on Algorithms and Complexity (CIAC '97), volume 1203 of Lecture Notes in Computer Science, pages 122-134. Springer, 1997.

F. Harary and A. Schwenk. A new crossing number of bipartite graphs. Utilitas Mathematica, 1:203-209, 1972.

M. Jünger, S. Leipert, and P. Mutzel. Level planarity testing in linear time. In S.H. Whitesides, editor, Proceedings of the 6th International Symposium on Graph Drawing (GD '98), volume 1547 of Lecture Notes in Computer Science, pages 224-237. Springer, 1998.

T. Schank. Algorithmen zur Visualisierung planarer partitionierter Graphen. Master's thesis, Universität Konstanz, 2001. http://www.inf.uni-konstanz.de/algo/lehre/theses/.