Planar segment visibility graphs

Hazel Everett 1 C.T. Hoang K. Kilakos M. Noy
1 ISA - Models, algorithms and geometry for computer graphics and vision
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
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 caracterize segment visibility graphs that do not contain the complete graph on 5 vertices as a minor, qnd 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 the complete graph on 4 vertices as a subgraph. In fact, we prove a stronger result: every set of n line segments determines at least n-3 empty convex quadrilaterals.
Type de document :
Article dans une revue
Computational Geometry, Elsevier, 2000, 16 (4), pp.235-243
Liste complète des métadonnées

https://hal.inria.fr/inria-00099259
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 08:52:11
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48

Identifiants

  • HAL Id : inria-00099259, version 1

Collections

Citation

Hazel Everett, C.T. Hoang, K. Kilakos, M. Noy. Planar segment visibility graphs. Computational Geometry, Elsevier, 2000, 16 (4), pp.235-243. 〈inria-00099259〉

Partager

Métriques

Consultations de la notice

160