**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.,

Send comments to *dan.archdeacon@uvm.edu*

December 2003