Number of segments of rectilinear drawings of a graph whose vertices are fixed on a plane
Toshihiko Takahashi, Yoji Kajitani · Electronics and Communications in Japan (Part III Fundamental Electronic Science) · 1991
Abstract The graph in which vertices are assigned different coordinates on the xy‐plane is called a rivetted graph. When a rivetted graph G is drawn so that each edge is composed of horizontal and/or vertical segments, it is called a rectilinear drawing of G. This study is an attempt to evaluate the total number of segments l(G) necessary and sufficient for the rectilinear drawing of a rivetted graph G. As a major result, it is shown that l(G)⩽4m and especially, l(G)⩽3m, if a vertex pair does not exist with the same x or y coordinate, using a construction algorithm with the computational complexity of O(m + ξ), where m is the number of edges and ξ is the number of isolated vertices in the graph. For examples of G, nontrivial lower bounds for l(G) also are considered.