SPIRALITY AND OPTIMAL ORTHOGONAL DRAWINGS

We deal with the problem of constructing the orthogonal drawing of a g raph with the minimum number of bends along the edges. The problem has been recently shown to be NP-complete in the general case. In this pa per we introduce and study the new concept of spirality, which is a me asure of how an orthogonal drawing is ''rolled up,'' and develop a the ory on the interplay between spirality and number of bends of orthogon al drawings. We exploit this theory to present polynomial time algorit hms for two significant classes of graphs: series-parallel graphs and 3-planar graphs. Series-parallel graphs arise in a variety of problems such as scheduling, electrical networks, data-flow analysis, database logic programs, and circuit layout. Also, they play a central role in planarity problems. Furthermore, drawings of 3-planar graphs are a cl assical field of investigation.