ALCOMFT-TR-03-188

Hans L. Bodlaender and Gerard Tel
Rectilinear Graphs and Angular Resolution
Utrecht. Work package 2. December 2003.

Abstract: In this note we show that a planar graph with angular resolution at least pi/2 can be drawn with all angles an integer multiple of pi/2, that is, in a rectilinear manner. Moreover, we show that for d != 4, d>2 having an angular resolution of 2pi / d does not imply that the graph can be drawn with all angles an integer multiple of 2pi / d. We argue that the exceptional situation for d=4 is due to the absence of triangles in the rectangular grid.

Keywords : Rectilinear drawing, plane graph, angular resolution, integer flow.

Postscript file: ALCOMFT-TR-03-188.ps.gz (143 kb).