Article ID Journal Published Year Pages File Type
4651083 Discrete Mathematics 2007 7 Pages PDF
Abstract

A triangulation TT of a compact 2-manifold is said to be a tree–tree triangulation if the graph of TT can be partitioned into two induced trees. Hence each tree–tree triangulation is a triangulation of the 2-sphere. Recognizing tree–tree triangulations among all simple spherical ones can be seen to be an NP-complete problem. Some (exponentially many) pairs of trees into which graphs of some simple triangulations can be partitioned are characterized. In particular, for a pair made up of any tree and any long enough path, there is a spherical triangulation whose graph is partitionable into that pair.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,