Rectangle-of-influence drawings of four-connected plane graphs: extended abstract
Kazuyuki Miura, Takao Nishizeki · 2005
A rectangle-of-influence drawing of a plane graph G is no vertex in the proper inside of the axis-parallel rectangle defined by the two ends of any edge. In this paper, weshow that any 4-connected plane graph G rectangle-of-influence drawing in an integer grid such that W + H n, where n is the numberofvertices in G, W is the width and H is the height of the grid. Thus the area W \\ThetaH of the grid is at most d(n;1)=2e\\Delta b(n;1)=2c. Our bounds on the grid sizes are optimal in a sense that there exist an infinite number of 4connected plane graphs whose drawings need grids such that W +H = n;1andW \\Theta H = d(n ; 1)=2e\\Delta b(n ; 1)=2c. We also showthatthe drawing can be found in linear time.