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.

Arrangement graphs, Hamiltonian path, Inducing path, Inducing polygon, Line arrangements
International Journal of Computational Geometry and Applications
School of Computer Science

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