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, Perugia, Italy , 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
ID Code:457

Repository Staff Only: item control page

References

D. Avis, Generating rooted triangulations without repetitions, Algorithmica, 16, (1996), pp. 618-632.

T. Beyer and S.M. Hedetniemi, Constant time generation of rooted trees, SIAM J. Comput., 9, (1980), pp. 706-712.

M. Chrobak and S. Nakano, Minimum-width grid drawings of plane graphs, Computational Geometry: Theory and Applications, 10, (1998), pp. 29-54.

H. de Fraysseix, J. Pach and R. Pollack, How to draw a planar graph on a grid, Combinatorica, 10, (1990), pp. 41-51.

L. A. Goldberg, Efficient algorithms for listing combinatorial structures, Cambridge University Press, New York, (1993).

J. E. Hopcroft and J.K. Wong, Linear time algorithm for isomorphism of planar graphs, Proc. of 6th STOC, (1974), pp. 172-184.

D. L. Kreher and D. R. Stinson, Combinatorial algorithms, CRC Press, Boca Raton, (1998).

Z. Li and S. Nakano, Efficient generation of plane triangulations without repetitions, Proc. ICALP2001, LNCS 2076, (2001), pp. 433-443.

B. D. McKay, Isomorph-free exhaustive generation, J. of Algorithms, 26, (1998), pp. 306-324.

W. Schnyder, Embedding planar graphs on the grid, Proc. 1st Annual ACM-SIAM Symp. on Discrete Algorithms, San Francisco, (1990), pp. 138-148.

R. A. Wright, B. Richmond, A. Adlyzko and B. D. McKay, Constant time generation of free trees, SIAM J. Comput., 15, (1986), pp. 540-548.