Paper Info
Title
Orthogonal Drawings of Series-Parallel Graphs with Minimum Bends
Abstract
In an orthogonal drawing of a planar graph $G$, each vertex is drawn as a point, each edge is drawn as a sequence of alternate horizontal and vertical line segments, and any two edges do not cross except at their common end. A bend is a point where an edge changes its direction. A drawing of $G$ is called an optimal orthogonal drawing if the number of bends is minimum among all orthogonal drawings of $G$. In this paper we give an algorithm to find an optimal orthogonal drawing of any given series-parallel graph of the maximum degree at most three. Our algorithm takes linear time, while the previously known best algorithm takes cubic time. Furthermore, our algorithm is much simpler than the previous one. We also obtain a best possible upper bound on the number of bends in an optimal drawing.
Year
DOI
Venue
2007
10.1137/060667621
SIAM Journal on Discrete Mathematics
Keywords
DocType
Volume
series-parallel graphs,minimum bends,optimal drawing,optimal orthogonal drawing,best algorithm,common end,cubic time,planar graph,orthogonal drawings,series-parallel graph,linear time,alternate horizontal,orthogonal drawing
Conference
22
Issue
ISSN
ISBN
4
0895-4801
3-540-30935-7
Citations 
PageRank 
References 
5
0.45
18
Authors
2
Name
Order
Citations
PageRank
Xiao Zhou132543.69
Takao Nishizeki21771267.08