Tree-Tree Triangulations

A simple triangulation G of the plane is a tree-tree triangulation if the vertices can be partitioned into two parts such that each part induces a tree. The dual of a tree-tree triangulation is a Hamiltonian planar cubic graph. It follows that recognizing if a triangulation is tree-tree is NP-complete.

Suppose that G is a tree-tree triangulations where the two induced trees are T_1 and T_2. Then G is a (T_1,T_2)-representation, and T_1 is triangulation compatable with T_2.

Problem: Determine which pairs {T_1,T_2} of trees are triangulation compatable.

The problem is related to Barnette’s conjecture, that every cubic bipartite planar graph is Hamiltonian. This is equivalent to asserting that every Eulerian triangulation is a tree-tree triangulation.

Some partial results are given in [SS], including a characterization of all possible T_2 if T_1 is a star. They mention that perhaps the most interesting open problem is:

Problem:  Characterize all trees T_2 that are triangulation compatable with a path T_1.

References:

[SS] G. Schaar and Z. Skupien, Pairs of trees in tree-tree triangulations, preprint.

Submitted by: Dan Archdeacon, Dept. of Math. and Stat., University of Vermont, Burlington, VT 05401-1455 USA