A graph is a visibility graph if its vertices v1,...,vn can be associated with disjoint horiziontal line segments s1,...,sn in the plane such that vi and vj are joined by an edge iff there exists a vertical line segment connecting si with sj without intersecting any other sk. Several authors have studied visibility representations of graphs in the context of integrated circuit layout. In particular, visibility graphs were investigated in the context of VLSI layout compaction. Among other results on visibility graphs the paper provides answers to questions posed in a paper of Tamassia and Tollis; for example it shows that deciding whether a given graph is a visibility graph is an NP-complete problem.
