Planar segment visibility graphs

Given a set of n disjoint line segments in the plane, the segment visibilit y graph is the graph whose 2n vertices correspond to the endpoints of the l ine segments and whose edges connect every pair of vertices whose correspon ding endpoints can see each other. In this paper we characterize and provid e a polynomial time recognition algorithm for planar segment visibility gra phs. Actually, we characterize segment visibility graphs that do not contai n the complete graph K-5 as a minor, and show that this class is the same a s the class of planar segment visibility graphs. We use and prove the fact that every segment visibility graph contains K-4 as a subgraph. In fact, we prove a stronger result: every set of n line segments determines at least n - 3 empty convex quadrilaterals. (C) 2000 Elsevier Science B.V. All right s reserved.