A study of rectangle-of-influence drawing algorithms of plane graphs

点击翻译按钮获取中文摘要

A drawing of a plane graph G is called a rectangle-of-influence drawing if all vertices of G are put on plane grid points, all edges are drawn as straight line segments without any edge-intersection and there is no vertex in the proper inside of the axis-parallel rectangle defined by the two ends of every edge. In this study, I improve a sufficient condition for a plane graph G to have a rectangle-of-influence drawing, and present a linear time algorithm to construct a rectangle-of-influence drawing of G on (n-1) x (n-1) integer grid if G satisfies the condition.