This paper addresses the classical graph drawing problem of designing an algorithm that computes an orthogonal representation with the minimum number of bends, by considering all possible planar embeddings of the graph. While the general problem has been shown to be NP-complete, polynomial time algorithms have been devised for graphs whose vertex degree is at most three. We show the first algorithm whose time complexity is exponential only in the number of vertices of degree four of the input graph. Our algorithm is further extended to handle graphs with vertices of degree higher than four. The analysis of the algorithm is supported by several experiments on the structure of a large set of input graphs.
Computing Orthogonal Drawings in a Variable Embedding Setting
DIDIMO, WALTER;LIOTTA, Giuseppe
1998
Abstract
This paper addresses the classical graph drawing problem of designing an algorithm that computes an orthogonal representation with the minimum number of bends, by considering all possible planar embeddings of the graph. While the general problem has been shown to be NP-complete, polynomial time algorithms have been devised for graphs whose vertex degree is at most three. We show the first algorithm whose time complexity is exponential only in the number of vertices of degree four of the input graph. Our algorithm is further extended to handle graphs with vertices of degree higher than four. The analysis of the algorithm is supported by several experiments on the structure of a large set of input graphs.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
