Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4651083 | Discrete Mathematics | 2007 | 7 Pages |
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
Günter Schaar, Zdzisław Skupień,