A More Compact Visibility Representation
Goos Kant · International Journal of Computational Geometry & Applications · 1997
In this paper we present a linear time and space algorithm for constructing a visibility representation of a planar graph on an [Formula: see text] grid, thereby improving the previous bound of (2n-5)×(n-1). To this end we build in linear time the 4-block tree of a planar graph, which improves previous time bounds. Moreover, this is the first time that the technique of splitting a graph into its 4-connected components is used successfully in graph drawing