05593561

a

05593561 Nakano, Shin-ichi Uno, Takeaki More efficient generation of plane triangulations. Liotta, Giuseppe (ed.), Graph drawing. 11th international symposium, GD 2003, Perugia, Italy, September 21--24, 2003. Revised papers. Berlin: Springer (ISBN 3-540-20831-3/pbk). Lect. Notes Comput. Sci. 2912, 273-282 (2004). 2004 Berlin: Springer EN

doi:10.1007/b94919

Summary: 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.