More Efficient Generation of Plane Triangulations

Nakano, Shin-Ichi and Uno, Takeaki (2004) More Efficient Generation of Plane Triangulations. In: Graph Drawing 11th International Symposium, GD 2003, September 21-24, 2003 , pp. 273-282(Official URL: http://dx.doi.org/10.1007/978-3-540-24595-7_25).

Full text not available from this repository.

Abstract

In this paper we give an algorithm to generate all biconnected plane triangulations having exactly n vertices including exactly r vertices on the outer face. The algorithm uses O(n) space in total and generates such triangulations without duplications in O(rn) time per triangulation, while the previous best algorithm generates such triangulations in O(r^{2}n) time per triangulation.

Item Type:	Conference Paper
Additional Information:	10.1007/978-3-540-24595-7_25
Classifications:	M Methods > M.600 Planar G Algorithms and Complexity > G.560 Geometry G Algorithms and Complexity > G.140 Augmentation
URI:	http://gdea.informatik.uni-koeln.de/id/eprint/457

Actions (login required)

View Item