Hamiltonian cycles in maximal planar graphs

Whitney proved long ago that every maximal planar graph with no separating triangles is Hamiltonian. However, the converse is not necessarily true, that is, there exist maximal planar graphs that are hamiltonian and have separating triangles. So what happens when a maximal planar graph has separating triangles? Is there still some condition under which we can say with certainty that it will be Hamiltonian as well?

One theorem of this kind was shown by Jackson and Yu.

Consider a maximal planar graph G with a separating triangle T. G can be decomposed into two graphs G_1 and G_2 such that G_1 \cup G_2 = G and G_1 \cap G_2 = T. If G_1 or G_2 still has separating triangles, then decompose them similarly. Eventually, we will be left with a collection S of maximal planar graphs without any separating triangles. Now, consider a graph whose nodes represent elements of the set S and there is an edge between two nodes if they share a separating traingle in G. Let’s call this graph D. The theorem by Jackson and Yu states that if D has maximum degree 3, then G is Hamiltonian.

This way of decomposing maximal planar graphs has been popular. It was first used by William Cunningham and Jack Edmonds in 1980. They proved several interesting results about the decomposition graph D.

Advertisements