{
  "id": "2303.16700",
  "version": "v1",
  "published": "2023-03-29T13:51:43.000Z",
  "updated": "2023-03-29T13:51:43.000Z",
  "title": "Disjointness Graphs of segments in R^2 are almost all Hamiltonian",
  "authors": [
    "J. Leaños",
    "Christophe Ndjatchi",
    "L. M. Ríos-Castro"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-03-29T13:51:43.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "edge disjointness graph",
      "order type isomorphism",
      "closed straight line segments",
      "general position",
      "full characterization"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}