Turn-regularity and optimal area drawings of orthogonal representations

Given an orthogonal representation H with n vertices and bends, we study th e problem of computing a planar orthogonal drawing of H with small area. Th is problem has direct applications to the development of practical graph dr awing techniques for information visualization and VLSI layout. In this pap er, we introduce the concept of turn-regularity of an orthogonal representa tion H, provide combinatorial characterizations of it, and show that if H i s turn-regular (i.e,, all its faces are turn-regular), then a planar orthog onal drawing of H with minimum area can be computed in O(n) time, and a pla nar orthogonal drawing of H with minimum area and minimum total edge length within that area can be computed in O(n(7/4) log n) time. We also apply ou r theoretical results to the design and implementation of new practical heu ristic methods for constructing planar orthogonal drawings. An experimental study conducted on a test suite of orthogonal representations of randomly generated biconnected 4-planar graphs shows that the percentage of turn-reg ular faces is quite high and that our heuristic drawing methods perform bet ter than previous ones. (C) 2000 Elsevier Science B.V. All rights reserved.