Drawing Planar Bipartite Graphs With Small Area

Biedl, Therese and Brandenburg, Franz J. (2005) Drawing Planar Bipartite Graphs With Small Area. In: Canadian Conference on Computational Geometry, August 10-12, 2005 , pp. 105-108. (In Press)

Postscript - Requires a viewer, such as GSview
Download (135kB) | Preview


In this paper, we study planar straight-line drawings of bipartite planar graphs. We show that these graphs admit drawings in an n/2 x (n/2-1) -grid, and that this is optimal. Our results generalize to triangle-free planar graphs.

Item Type: Conference Paper
Classifications: G Algorithms and Complexity > G.070 Area / Edge Length
URI: http://gdea.informatik.uni-koeln.de/id/eprint/604

Actions (login required)

View Item View Item