×

Triangulations with circular arcs. (English) Zbl 1311.68162

van Kreveld, Marc (ed.) et al., Graph drawing. 19th international symposium, GD 2011, Eindhoven, The Netherlands, September 21–23, 2011. Revised selected papers. Berlin: Springer (ISBN 978-3-642-25877-0/pbk). Lecture Notes in Computer Science 7034, 296-307 (2012).
Summary: 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.
For the entire collection see [Zbl 1232.68014].

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68R10 Graph theory (including graph drawing) in computer science

Software:

Voronoi
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aichholzer, O., Aigner, W., Aurenhammer, F., Čech Dobiášová, K., Jüttler, B.: Arc triangulations. In: Proc. 26th European Workshop Comput. Geometry, pp. 17–20 (2010)
[2] 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) · Zbl 1319.65016
[3] 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) · Zbl 1233.65014 · doi:10.1142/S0218195911003548
[4] 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)
[5] 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) · Zbl 1027.76041 · doi:10.1002/nme.542
[6] Burkard, R.E., Rendl, F.: Lexicographic bottleneck problems. Operations Research Letters 10, 303–308 (1991) · Zbl 0744.90069 · doi:10.1016/0167-6377(91)90018-K
[7] Carré, B.: Graphs and networks. Oxford University Press (1979)
[8] 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) · Zbl 0953.05071 · doi:10.1007/3-540-46648-7_12
[9] Chew, L.P.: Constrained Delaunay triangulations. Algorithmica 4, 97–108 (1989) · Zbl 0664.68042 · doi:10.1007/BF01553881
[10] Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing–Algorithms for the Visualization of Graphs. Prentice-Hall (1999) · Zbl 1057.68653
[11] Di Battista, G.D., Vismara, L.: Angles of planar triangular graphs. SIAM J. Discrete Mathematics 9, 349–359 (1996) · Zbl 0862.05033 · doi:10.1137/S0895480194264010
[12] 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) · Zbl 1314.68227 · doi:10.1007/978-3-642-18469-7_18
[13] 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) · Zbl 0686.68035 · doi:10.1016/0304-3975(89)90133-3
[14] 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) · Zbl 1161.68661 · doi:10.7155/jgaa.00140
[15] 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) · doi:10.1007/978-3-540-31843-9_46
[16] 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) · Zbl 0797.05042 · doi:10.1137/0222063
[17] Fortune, S.: Voronoi diagrams and Delaunay triangulations. Computing in Euclidean Geometry. LN Series on Computing, vol. 4, pp. 225–265. World Scientific (1995)
[18] Goodrich, M.I., Wagner, C.G.: A framework for drawing planar graphs with curves and polylines. J. Algorithms 37, 399–421 (2000) · Zbl 0964.68104 · doi:10.1006/jagm.2000.1115
[19] Karp, R.M.: A characterization of the minimum cycle mean in a digraph. Discrete Mathematics 23, 309–311 (1978) · Zbl 0386.05032 · doi:10.1016/0012-365X(78)90078-X
[20] 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) · doi:10.1109/SFCS.1977.21
[21] Malitz, S., Papakostas, A.: On the angular resolution of planar graphs. In: Proc. 24th Ann., pp. 527–538 (1992) · Zbl 0824.05018 · doi:10.1145/129712.129764
[22] 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) · Zbl 0767.90077 · doi:10.1016/0377-2217(92)90347-C
[23] Nishizeki, T., Rahman, M.S.: Planar graph drawing. World Scientific (2004) · Zbl 1070.68124 · doi:10.1142/5648
[24] Pedoe, D.: A course of geometry for colleges and universities. Cambridge University Press (1970) · Zbl 0213.22001
[25] Rote, G.: Two solvable cases of the traveling salesman problem. PhD Thesis, TU Graz, Institute for Mathematics (1988)
[26] Shewchuk, J.: What is a good linear element? Interpolation, conditioning, and quality measures. In: Proc. 11th International Meshing Roundtable, pp. 115–126 (2002)
[27] Shostak, R.: Deciding linear inequalities by computing loop residues. Journal of the ACM 28, 769–779 (1981) · Zbl 0468.68073 · doi:10.1145/322276.322288
[28] Sugiyama, K.: Graph Drawing and Applications for Software and Knowledge Engineers. World Scientific (2002) · Zbl 1011.68068 · doi:10.1142/4902
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.