Hamiltonian Cycles in the
Vertex-Adjacency Dual








  1. Garey, M. R. and Johnson, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman, 1983.

  2. Eppstein, D., The traveling salesman problem for cubic graphs. In Proc. 8th Worksh. Algorithms and Data Structures(2003), Dehne F., Sack J.-R.,, Smid M., (Eds.), no. 2748 in Lecture Notes in Computer Science, Springer-Verlag,pp. 307–318.

  3. E. M. Arkin, M. Held, J. S. B. Mitchell, and S. S. Skiena. Hamiltonian triangulations for fast rendering. Visual Computing, 12(9):429–444, 1996.

  4. J. J. Bartholdi III and P. Goldsman. Multiresolution indexing of triangulated irregular networks. IEEE Transactions on Visualization and Computer Graphics, 10(3):1–12, 2004.

  5. J. J. Bartholdi III and P. Goldsman. The vertexadjacency dual of a triangulated irregular network has a hamiltonian cycle. Operations Research Letters, 32:304–308, 2004.

  6. Z. Chen, M. Grigni, and C. H. Papadimitriou. Map graphs. Journal of the ACM (JACM), 49(2):127–138, 2002.

  7. E. D. Demaine, D. Eppstein, J. Erickson, G. W. Hart, and J. O’Rourke. Vertex-unfoldings of simplicial manifolds. In Proceedings of the eighteenth annual symposium on Computational geometry, pages 237–243, Barcelona, Spain, 2002.

  8. R. Flatland. On sequential triangulations of simple polygons. In Proceedings of the 16th Canadian Conference on Computational Geometry, pages 112–115, 1996.

  9. M. Gopi and D. Eppstein. Single-strip triangulation of manifolds with arbitrary topology. In Computer Graphics Forum (EUROGRAPHICS), volume 23, 2004.

  10. F. Harary and A. Schwenk. Trees with hamiltonian square. Mathematika, 18:138–140, 1971.

  11. M. Isenburg. Triangle strip compression. In Proceedings of Graphics Interface 2000, pages 197–204, Montreal, Quebec, Canada, May 2000.

  12. G. Taubin and J. Rossignac. Geometric compression through topological surgery. ACM Transactions on Graphics, 17(2):84–115, 1998.

This page was prepared by Perouz Taslakian - December 2004