Disjointness Graphs of segments in R^2 are almost all Hamiltonian

J. Leaños, Christophe Ndjatchi, L. M. Ríos-Castro

Published 2023-03-29Version 1

Let P be a set of n >= 2 points in general position in R^2. The edge disjointness graph D(P) of P is the graph whose vertices are all the closed straight line segments with endpoints in P, two of which are adjacent in D(P) if and only if they are disjoint. In this note, we give a full characterization of all those edge disjointness graphs that are hamiltonian. More precisely, we shall show that (up to order type isomorphism) there are exactly 8 instances of P for which D(P) is not hamiltonian. Additionally, from one of these 8 instances, we derive a counterexample to a criterion for the existence of hamiltonian cycles due to A. D. Plotnikov in 1998.