3
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\begingroup$ Just checking: by "simple-polygonal tour", do you mean 'circuit'='graph-theoretic cycle'='two-regular subgraph'? While I know that 'polygon' is a (rare) synonym, it is considered old-fashioned in graph-theory today. (Incidentally, I recommend 'circuit', and so does e.g. A. Bondy in the Chapter 'Basic Graph Theory' in Volume I of the 'Handbook of Graph Theory'. Another question: you ask about "planar embeddings of Hamiltonian graphs", but then you give the iconic two examples of non-planar graphs ($K^5$ and $K^{3,3}$). Why? These do not have any planar embedding. Would you please clarify? $\endgroup$
    – Peter Heinig
    Commented Aug 20, 2017 at 6:03
  • $\begingroup$ The gist of the question is not clear (to me), and I think it should be clarified. First and foremost, there is a confusing (to me) tension between what the unusual term "simply-polygonal tour" might be trying to say, and what logically is the case in a planar graph: even if the shape of the circuit in a specified embedding matters to you, it is a fact that: 'simple-polygonal tour in the embedding'='circuit in the embedding'. In this sense, I do not see what the use of 'simple-polygonal tour' is meant to achieve. $\endgroup$
    – Peter Heinig
    Commented Aug 20, 2017 at 6:57
  • $\begingroup$ Second, the use of "maximum number" (or "maximal number" in the original of the OP), clearly signals that some maximization is meant. But what set are you maximizing the "number of simple-polygonal tours" over? To me, the only interpretation of the question seems to be: What noteworthy general statements of the following form are known: For every $G$ be a finite abstract planar Hamiltonian graph, $\max\{\text{numberofcircuits}(\eta(G))\colon\text{$ \eta\colon \lvert G\rvert\rightarrow\mathbb{R}^2$ an embedding }\}$ $\leq$ $\text{some noteworthy statement}$. Is it this what you mean? If so,[..] $\endgroup$
    – Peter Heinig
    Commented Aug 20, 2017 at 7:04
  • $\begingroup$ [..] then at least for graphs which are in addition assumed to be vertex-$3$-connected (which I guess most of the graphs you care about are anyway), this maximization is trivial, in that by a theorem usually (yet perhaps quite ahistorically) attributed to H. Whitney, there is essentially only one embedding, so the maximization is over a one-element set. Would you please clarify? $\endgroup$
    – Peter Heinig
    Commented Aug 20, 2017 at 7:06
  • 1
    $\begingroup$ Echoing Peter's comments: I have no idea what this question is asking. $\endgroup$
    – Brendan McKay
    Commented Aug 20, 2017 at 8:32

2 Answers 2

Reset to default
5
$\begingroup$

It is known that the number of non-crossing spanning cycles (called "simple polygonalizations") of $n$ points in the plane can be as low as $1$ (for points in convex position) and as high as $4.64^n$, and that it is never higher than $94^n$. See:

On the Number of Crossing‐Free Matchings, Cycles, and Partitions. Micha Sharir and Emo Welzl. SIAM J. Comput. 36(3): 695–720, 2006.

Improve this answer
$\endgroup$
4
$\begingroup$

Slightly later, and less formally published reference, than David E.'s citation:

Sharir, Micha, Adam Sheffer, and Emo Welzl. "Counting plane graphs: Perfect matchings, spanning cycles, and Kasteleyn's technique." Proceedings 28th Symposium on Computational Geometry. ACM, 2012. (arXiv abs.)

[...] a new upper bound of $O(54.5^N)$ on the number of crossing-free straight-edge spanning cycles that can be embedded over any specific set of $N$ points in the plane, improving upon the previous best upper bound $O(68.7^N)$.

Fig5

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .