Hamiltonicity and colorings of arrangement graphs
Stefan Felsner, Ferrán Hurtado, Marc Noy, Ileana Streinu · Symposium on Discrete Algorithms · 2000
We study connectivity Hamilton path and Hamil ton cycle decomposition edge and vertex col oring for geometric graphs arising from pseudoline a ne or projective and pseudocircle spherical arrangements While arrangements as geometric objects are well studied in discrete and computa tional geometry their graph theoretical properties seem to have received little attention so far In this paper we show that they provide well structured ex amples of families of planar and projective planar graphs with very interesting properties Most prominently spherical arrangements admit decom positions into two Hamilton cycles and edge color ings but other classes have interesting properties as well connectivity vertex coloring or Hamilton paths and cycles We show a number of negative results as well there are projective arrangements which cannot be vertex colored A number of con jectures and open questions accompany our results