Properties of Arrangements Graphs

Prosenjit Bose Hazel Everett 1 Steve Wismath
1 ISA - Models, algorithms and geometry for computer graphics and vision
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : An arrangement graph G is the abstract graph obtained from an arrangement of lines L, in general position, by associating vertices of G with the intersection points of L, and the edges of G with the line segments joining the intersection points of L. A simple polygon (respectively path) of n sides in general position, induces a set of n lines by extension of the line segments into lines. The main results of this paper are : (i) given a graph G, it is NP-Hard to determine if G is the arrangement graph of some set of lines (ii) there are non-Hamiltonian arrangement graphs for arrangements of six lines and for odd values of n>6 lines, (iii) all arrangements of n lines contain a subarrangement of size sqrt(n-1)+1 with an inducing polygon (iv) all arrangements on n lines contain an inducing path consisting of n segments and (v) all arrangements on n hyperplanes in R^d contain a simple inducing polygonal cycle of size n.
Type de document :
Article dans une revue
International Journal of Computational Geometry and Applications, World Scientific Publishing, 2003, 13 (6), pp.447-462
Liste complète des métadonnées

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

Identifiants

  • HAL Id : inria-00099529, version 1

Collections

Citation

Prosenjit Bose, Hazel Everett, Steve Wismath. Properties of Arrangements Graphs. International Journal of Computational Geometry and Applications, World Scientific Publishing, 2003, 13 (6), pp.447-462. 〈inria-00099529〉

Partager

Métriques

Consultations de la notice

182