Minimum Segment Drawings of Series-Parallel Graphs with the Maximum Degree Three

A minimum segment drawing Γ of a planar graph G is a straight line drawing of G that has the minimum number of segments among all straight line drawings of G. In this paper, we give a linear-time algorithm for computing a minimum segment drawing of a series-parallel graph with the maximum degree three.To the best of our knowledge, this is the first algorithm for computing minimum segment drawings of an important subclass of planar graphs