An Algorithm for Straight-Line Drawing of Planar Graphs

We present a new algorithm for drawing planar graphs on the plane. It can be viewed as a generalization of the algorithm of Chrobak and Payne, which, in turn, is based on an algorithm by de Fraysseix, Pach, and Pollack. Our algorithm improves the previous ones in that it does not require a preliminary triangulation step; triangulation proves problematic in drawing graphs ``nicely,'' as it has the tendency to ruin the structure of the input graph. The new algorithm retains the positive features of the previous algorithms: it embeds a biconnected graph of n vertices on a grid of size (2n-4) x (n-2) in linear time. We have implemented the algorithm as part of a software system for drawing graphs nicely.

Authors and Affiliations

1. Department of Applied Mathematics and Computer Science, The Weizmann Institute of Science, Rehovot, Israel. harel@wisdom.weizmann.ac.il, , , , , , IL

   D. Harel

2. Current address: Orbot Instruments Ltd., Yavneh Industrial Zone, P.O. Box 601, Yavneh, Israel. meir_sardas@amat.com., , , , , , IL

   M. Sardas

Received September 21, 1995; revised March 15, 1996.

Reprints and permissions