Simple linear algorithm for no-bend orthogonal drawings of series-parallel graphs

Abstract

This thesis deals with no-bend orthogonal drawings of series-parallel graphs. A no-bend orthogonal drawing of a series-parallel graph is a drawing, in which each vertex is drawn as a point, each edge is drawn as a single horizontal or vertical line segment and any two edges do not cross except at their common end. A series-parallel graph is said to have a no-bend orthogonal drawing if at least one of its plane embeddings has a no-bend orthogonal drawing. In this thesis we give a simple linear algorithm to examine whether a series-parallel graph G of maximum degree three has a no-bend orthogonal drawing and to find one if G has. Our algorithm is conceptually simpler than the previous known linear algorithm.