MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 8 down vote accepted

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.

share|cite|improve this answer

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.)

share|cite|improve this answer
    
Thank you for the reference! But what about Hamiltonian path? – Ping Jan 17 at 1:16
1  
I should clarify that by a planar triangulation I mean this: mathworld.wolfram.com/TriangulatedGraph.html The second example is not a planar triangulation. – Ping Jan 17 at 1:59
    
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. – Joseph O'Rourke Jan 17 at 2:30

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

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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