Petrie words

A hamiltonian cycle in a map can seem very indirect, so it is surprising that some hamiltonian cycles are straight. That is, they are as straight as possible under the constraints of the map. "As straight as possible" in a 3-regular map means that left turns alternate with right turns. Such a cycle is called a petrie cycle; and, if it visits all the vertices exactly once, it is called a petrie hamiltonian cycle.

The hamiltonian cycle of the tetrahedron may not seem particularly straight, but it is as straight as the map permits: it alternates left and right turns. It is therefore a petrie hamiltonian cycle.

An undip word intrinsically defines a hamiltonian cycle; if the letters alternate in handedness, then it defines a petrie hamiltonian cycle. (The alternation needs to continue when following upon the last letter with the first, but the parity of the number of letters guarantees this.)

Ivanco, Jendrol, and Tkac in Note on Petrie and Hamiltonian cycles in cubic polyhedral graphs, give a clever way to turn any hamiltonian cycle in a trivalent map into a petrie hamiltonian cycle in a related, somewhat larger, trivalent map. Anywhere the hamiltonian cycle makes a "wrong" (i.e., non-petrie) turn, we fix the problem by simply truncating the vertex.

This procedure has an easy interpretation in undip. Each letter in the undip word represents a vertex. To truncate a "wrong-turn" vertex we use the insertion rule to insert an emit/absorb (a.k.a., open/close) episode of the opposite handedness adjacent to the problem vertex, and then we use the shuffle rule to make this episode enclose the problem vertex. That restores the proper alternation of left and right around that vertex.

To take the simplest example, the word

ud

is non-petrie because the second letter has the same handedness as the preceding letter. Employing our strategy, we can insert an emit/absorb episode of the opposite handedness next to the problem letter:

udnp

Then shuffle to enclose the problem letter d:

undp

If we make it a rule that the first letter of a non-petrie word does not need any correcting, then every undip word has a canonical petrie descendant.