|
|||||
|
|
Planar segment visibility graphs |
|
| Authors: | H Everett C T Hong K Kilakos M Noy |
| Institution: | a LORIA, 615, rue du Jardin Botanique, B.P. 101, 54602 Villers-les-Nancy cedex, France b Department of Mathematical Sciences, Lakehead University, 955 Oliver Road, Thunder Bay, P7B 5E1, Canada c Department of Mathematics, London School of Economics, Houghton Street, London, WC2A 2AE, England, UK d Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, 5 Pau Gargallo, 08028 Barcelona, Spain |
| Abstract: | Given a set of n disjoint line segments in the plane, the segment visibility graph is the graph whose 2n vertices correspond to the endpoints of the line segments and whose edges connect every pair of vertices whose corresponding endpoints can see each other. In this paper we characterize and provide a polynomial time recognition algorithm for planar segment visibility graphs. Actually, we characterize segment visibility graphs that do not contain the complete graph K5 as a minor, and show that this class is the same as the class of planar segment visibility graphs. We use and prove the fact that every segment visibility graph contains K4 as a subgraph. In fact, we prove a stronger result: every set of n line segments determines at least n−3 empty convex quadrilaterals. |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ | |