We deal with the problem of constructing the orthogonal drawing of a graph with the minimum number of bends along the edges. The problem has been recently shown to be NPcomplete in the general case. In this paper we introduce and study the new concept of spirality, which is a measure of how an orthogonal drawing is “rolled up,” and develop a theory on the interplay between spirality and number of bends of orthogonal drawings. We exploit this theory to present polynomial time algorithms 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 classical field of investigation.
Spirality and Optimal Orhogonal Drawings
LIOTTA, Giuseppe;
1998
Abstract
We deal with the problem of constructing the orthogonal drawing of a graph with the minimum number of bends along the edges. The problem has been recently shown to be NPcomplete in the general case. In this paper we introduce and study the new concept of spirality, which is a measure of how an orthogonal drawing is “rolled up,” and develop a theory on the interplay between spirality and number of bends of orthogonal drawings. We exploit this theory to present polynomial time algorithms 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 classical field of investigation.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
