We establish new lower and upper bounds for the real number graph labelling problem. As an application, we consider a problem of Griggs to determine the optimum spans of $L(p,q)$-labellings of the in...
Let $A$ be an $n$-point set in the plane. A discrete X-ray of $A$ in direction $u$ gives the number of points of $A$ on each line parallel to $u$. We define $F(k)$ as the maximum number $n$ such that...
You are not logged in to this journal. Log in
Orthogonal Drawings of Series-Parallel Graphs with Minimum Bends
SIAM J. Discrete Math. Volume 22, Issue 4, pp. 1570-1604 (2008)
Published October 17, 2008
Connotea
CiteULike
del.icio.us
BibSonomy
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.
©2008 Society for Industrial and Applied Mathematics| History: | Received August 16, 2006; accepted May 15, 2008; published October 17, 2008 |
| Permalink: | http://dx.doi.org/10.1137/060667621 |
KEYWORDS and AMS
PUBLICATION DATA
SIAM