6
$\begingroup$

What about a Hamiltonian path in a triangulation of an n-gon? If not, how long is the longest path?

$\endgroup$
8
$\begingroup$

There are two planar triangulations on 14 vertices without hamiltonian paths. This is the smallest size. For sure these are well-known.

no hamiltonian path

Those answer the question for $n=3$. For $n=4$ the first examples appear at 12 vertices. Same for $n=5$. For $n=6$ one with 10 vertices. For $n=7$ one with 11 vertices. And so forth.

$\endgroup$
7
$\begingroup$

It is a famous theorem of Whitney (1931*) that a $4$-connected planar triangulation has a Hamiltonian cycle.


         
          Example of non-Hamiltonian triangulation from Joseph Malkevitch,
              obviously not $4$-connected: removing $3$ vertices (surrounding one) disconnects.
              (A graph is $4$-connected if it requires removal of $4$ vertices to disconnect it.)


* H Whitney. A theorem on graphs. Ann. of Math., 32 (1931), pp. 378–390.

In response to the OP's query:


          TriNoHP
          A connected triangulated graph with no Hamiltonian path.


Perhaps the OP may be interested in this paper:

Arkin, Esther M., Martin Held, Joseph SB Mitchell, and Steven S. Skiena. "Hamiltonian triangulations for fast rendering." The Visual Computer. 12, No. 9 (1996): 429-444.
(Springer link.)

$\endgroup$
  • $\begingroup$ Thank you for the reference! But what about Hamiltonian path? $\endgroup$ – OHO Jan 17 '16 at 1:16
  • 1
    $\begingroup$ I should clarify that by a planar triangulation I mean this: mathworld.wolfram.com/TriangulatedGraph.html The second example is not a planar triangulation. $\endgroup$ – OHO Jan 17 '16 at 1:59
  • $\begingroup$ The answer is still No, but now you need a maximal planar triangulated graph with at least $8$ "separating triangles." This is easily constructed, and it has no Hamiltonian path. $\endgroup$ – Joseph O'Rourke Jan 17 '16 at 2:30
5
$\begingroup$

See the answer to this question. The magic word is "Kleetope". For more information than you imagined possible, see Guido Helden's Thesis.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.