Triangulations with Circular Arcs

Aichholzer, Oswin and Aigner, Wolfgang and Aurenhammer, Franz and Čech Dobiášová, Kateřina and Jüttler, Bert and Rote, Günter (2012) Triangulations with Circular Arcs. In: Graph Drawing 19th International Symposium, GD 2011, September 21-23, 2011, Eindhoven, The Netherlands , pp. 296-307 (Official URL: http://dx.doi.org/ 10.1007/978-3-642-25878-7_29).

Full text not available from this repository.

Abstract

An important objective in the choice of a triangulation is that the smallest angle becomes as large as possible. In the straight-line case, it is known that the Delaunay triangulation is optimal in this respect. We propose and study the concept of a circular arc triangulation— a simple and effective alternative that offers flexibility for additionally enlarging small angles—and discuss its applications in graph drawing.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-25878-7_29
Classifications:P Styles > P.300 Curved
ID Code:1264

Repository Staff Only: item control page

References

Aichholzer, O., Aigner, W., Aurenhammer, F., Čech Dobiášováech, K., Jüttler, B.: Arc triangulations. In: Proc. 26th European Workshop Comput. Geometry, pp. 17–20 (2010)

Aichholzer, O., Rote, G., Schulz, A., Vogtenhuber, B.: Pointed drawings of planar graphs. In: Proc. 19th Ann. Canadian Conf. Comput. Geometry, pp. 237–240 (2007)

Aichholzer, O., Aurenhammer, F., Hackl, T., Juettler, B., Oberneder, M., Sir, Z.: Computational and structural advantages of circular boundary representation. Int’l J. Computational Geometry & Applications 21, 47–69 (2011)

Bern, M., Eppstein, D.: Mesh generation and optimal triangulation. Computing in Euclidean Geometry. LN Series on Computing, vol. 4, pp. 47–123. World Scientific (1995)

Boivin, C., Ollivier-Gooch, C.: Guaranteed-quality triangular mesh generation for domains with curved boundaries. International Journal for Numerical Methods in Engineering 55, 1185–1213 (2002)

Burkard, R.E., Rendl, F.: Lexicographic bottleneck problems. Operations Research Letters 10, 303–308 (1991)

Carré, B.: Graphs and networks. Oxford University Press (1979)

Cheng, C.C., Duncan, C.A., Goodrich, M.T., Kobourov, S.G.: Drawing Planar Graphs With Circular Arcs. In: Kratochvíl J. (ed.) GD 1999. LNCS, vol. 1731, pp. 117–126. Springer, Heidelberg (1999)

Chew, L.P.: Constrained Delaunay triangulations. Algorithmica 4, 97–108 (1989)

Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing—Algorithms for the Visualization of Graphs. Prentice-Hall (1999)

Di Battista, G.D., Vismara, L.: Angles of planar triangular graphs. SIAM J. Discrete Mathematics 9, 349–359 (1996)

Duncan, C.A., Eppstein, D., Goodrich, M.T., Kobourov, S.G., Nöllenburg, M.: Lombardi Drawings of Graphs. In: Brandes, U., Cornelsen, S. (eds.) GD 2010. LNCS, vol. 6502, pp. 195–207. Springer, Heidelberg (2011)

Edelsbrunner, H., Rote, G., Welzl, E.: Testing the necklace condition for shortest tours and optimal factors in the plane. Theor. Comput. Sci. 66, 157–180 (1989)

Efrat, A., Erten, C., Kobourov, S.G.: Fixed-Location Circular-Arc Drawing of Planar Graphs. Journal of Graph Algorithms and Applications 11, 145–164 (2007)

Finkel, B., Tamassia, R.: Curvilinar Graph Drawing Using The Force-Directed Method. In: Pach, J. (ed.) GD 2004. LNCS, vol. 3383, pp. 448–453. Springer, Heidelberg (2005)

Formann, M., Hagerup, T., Haralambides, J., Kaufmann, M., Leighton, F.T., Symvonis, A., Welzl, E., Wöginger, G.: Drawing graphs in the plane with high resolution. SIAM J. Computing 22, 1035–1052 (1993)

Fortune, S.: Voronoi diagrams and Delaunay triangulations. Computing in Eu-clidean Geometry. LN Series on Computing, vol. 4, pp. 225–265. World Scientific (1995)

Goodrich, M.I., Wagner, C.G.: A framework for drawing planar graphs with curves and polylines. J. Algorithms 37, 399–421 (2000)

Karp, R.M.: A characterization of the minimum cycle mean in a digraph. Discrete Mathematics 23, 309–311 (1978)

Lloyd, E.L.: On triangulations of a set of points in the plane. In: Proc. 18th IEEE Symp. on Foundations of Computer Science, pp. 228–240 (1977)

Malitz, S., Papakostas, A.: On the angular resolution of planar graphs. In: Proc. 24th Ann., pp. 527–538 (1992)

Marchi, E., Oviedo, J.A.: Lexicographic optimality in the multiple objective linear programming: The nucleolar solution. European Journal of Operational Research 57, 355–359 (1992)

Nishizeki, T., Rahman, M.S.: Planar graph drawing. World Scientific (2004)

Pedoe, D.: A course of geometry for colleges and universities. Cambridge University Press (1970)

Rote, G.: Two solvable cases of the traveling salesman problem. PhD Thesis, TU Graz, Institute for Mathematics (1988)

Shewchuk, J.: What is a good linear element? Interpolation, conditioning, and quality measures. In: Proc. 11th International Meshing Roundtable, pp. 115–126 (2002)

Shostak, R.: Deciding linear inequalities by computing loop residues. Journal of the ACM 28, 769–779 (1981)

Sugiyama, K.: Graph Drawing and Applications for Software and Knowledge Engineers. World Scientific (2002)