Properties of arrangement graphs
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: Given a graph G, it is NP-Hard to determine if G is the arrangement graph of some set of lines. There are non-Hamiltonian arrangement graphs for arrangements of six lines and for odd values of n > 6 lines. All arrangements of n lines contain a subarrangement of size √n- 1 + 1 with an inducing polygon. All arrangements on n lines contain an inducing path consisting of n line segments. A Java applet implementing the algorithm for determining such a path is also provided. All arrangements on n hyperplanes in Rd contain a simple inducing polygonal cycle of size n.
|Keywords||Arrangement graphs, Hamiltonian path, Inducing path, Inducing polygon, Line arrangements|
|Journal||International Journal of Computational Geometry and Applications|
Bose, P, Everett, H. (Hazel), & Wismath, S. (Stephen). (2003). Properties of arrangement graphs. International Journal of Computational Geometry and Applications, 13(6), 447–462. doi:10.1142/S0218195903001281