Rectangle-of-Influence Drawings of Four-Connected Plane Graphs

Miura, K. and Nishizeki, T.

A rectangle-of-influence drawing of a plane graph G is a straight-line planar drawing of G such that there is no vertex in the proper inside of the axis-parallel rectangle defined by the two ends of any edge. In this paper, we show that any 4-connected plane graph G with four or more vertices on the outer face has a rectangle-of-influence drawing in an integer grid such that W + H <= n, where n is the number of vertices in G, W is the width and H is the height of the grid. Thus the area W x H of the grid is at most [(n-1)/2].[(n=1)/2]. Our bounds on the grid sizes are optimal in a sense that there exist an in nite number of 4-connected plane graphs whose drawings need grids such that W +H = n-1 and W x H = [(n-1)/2].[(n=1)/2]. We also show that the drawing can be found in linear time.

Cite as: Miura, K. and Nishizeki, T. (2005). Rectangle-of-Influence Drawings of Four-Connected Plane Graphs. In Proc. Asia Pacific Symposium on Information Visualisation (APVIS2005), Sydney, Australia. CRPIT, 45. Hong, S.-H., Ed. ACS. 75-80.

(from crpit.com) (local if available)