Plane Representations of Graphs and Visibility between Parallel Segments.
Roberto Tamassia, Ioannis G. Tollis · Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign) · 1985
Several layout compaction strategies for VLSI are based on the concept of visibility between parallel segments, where we say that two parallel segments of a given set are visible if they can be joined by a segment orthogonal to them, which does not intersect any other segment.In this paper, we study visibility representations of graphs, which are constructed by mapping vertices to horizontal segments, and edges to vertical segments drawn between visible vertex-segments.Clearly, every graph th at admits this representation m ust be planar.We consider three types of visibility representations, and we give complete characterizations of the classes of graphs th at admit them.Furthermore, we present linear time algorithms for testing the existence of and constructing visibility representations of planar graphs.