A unified approach to visibility representations of planar graphs (Q1085167)

In the so-called visibility representations of planar graphs, vertices are represented by horizontal segments and edges by vertical segments that intersect the horizontal ones in case of their incidence. The authors consider three types of visibility representations and give complete characterization of the classes of graphs that admit them. In particular, a problem of Mel'nikov, posed at the 6th Hung. Colloquium on Combinatorics, Eger 1981, is settled. Further, linear time algorithms for testing the existence of and constructing visibility representations of planar graphs are presented. Among them, a variant of the Otten - van Wijk algorithm [Circuits and Systems, Proc. IEEE Int. Symp. 914-918 (1978); see also \textit{P. Rosenstiehl} and \textit{R. E. Tarjan}, Discrete Comput. Geom. 1, 343-353 (1986; see the review below)] is contained.