Skip to main content
5 of 5
Corrected the title of the question and added the graph-drawing tag
Manfred Weis
  • 13.2k
  • 4
  • 34
  • 76

Number Associated with Straight-line Drawings of Hamiltonian Graphs

Is there anything known about the maximum number of simple-polygonal Hamilton cycles that a straight-line drawing of a Hamiltonian graph can have?

Put differently, if the vertices of a Hamilton graph are mapped to points of the euclidean plane and the edges to straight-line segments connecting the images of their adjacent vertices, how many of the graph's Hamilton cycles are then maximally be mapped to simple polygons.

Take for example $K_5$: if the images of all five vertices are in convex configuration, then exactly one Hamilton cycle is mapped to a simple polygon; if only four vertices are in convex configuration, then four Hamilton cycles are mapped to simple polygons, and if finally only three points are in convex configuration, then six of the Hamiltion cycles are mapped to simple polygons - in no case is it possible to place the points in such a way, that all twelve Hamilton cycles are mapped to simple polygons. So, in case of $K5$ the maximal number I am looking for, would be $6$, provided, I counted right.

Remarks.

  • I am especially interested in $K_5$ and $K_{3,3}$, mainly, because due to Kuratowski's characterization of planar graphs, one can be sure that permutations of $5$ (resp. $6$) cities, i.e. those permutations which correspond to a Hamilton circuit, can't appear in that order in the optimal tour through all $n$ cities; with $K_4$, this is not so.

  • Letting $p$ denote the maximum number of simple polygonal tours and $h$ the number of Hamiltonian tours, $h-p$ permutations of a subset of $m$ cities can be excluded from the optimal tour through all $n$ cities.

Manfred Weis
  • 13.2k
  • 4
  • 34
  • 76