About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Abstract
Given a set S = {s1, s2,..., sn} of vertical line segments, s1, sj see each other if there is a horizontal line segment which intersects them, but does not intersect any other line segment between them. A visibility graph G of vertices {v1, v2,..., vn} is put into a one-to-one correspondence with S, such that si corresponds to v1, and edge {vi, vj} exists in G iff si, sj see each other. We prove that any visibility graph G is ipo-triangular, that is, it can be transformed into a planar multigraph with all triangular finite faces, by successive duplications of existing edges of G. Conversely we prove that any ipo-triangular graph is a visibility graph for some set S. © 1987.