Optimal rectilinear drawing of a graph whose vertices are fixed on a plane

The concept of the riveted graph (G) is introduced. The minimum number l(G) of line segments for a rectilinear drawing of G is evaluated. Some elementary properties of rectilinear drawings are discussed. It is shown that l(G )⩽4m for any G where m is the number of edges. It is shown that l(G)⩽3m if G has no pair of vertices with the same x or y coordinate. The proof of each result includes an O( m) time algorithm of drawing. Some results on the lower bounds of l(G) for a given graph G are presented