CelticGraph: drawing graphs as Celtic knots and links. (English) Zbl 07869492
Bekos, Michael A. (ed.) et al., Graph drawing and network visualization. 31st international symposium, GD 2023, Isola delle Femmine, Palermo, Italy, September 20–22, 2023. Revised selected papers. Part I. Cham: Springer. Lect. Notes Comput. Sci. 14465, 18-35 (2023).
Summary: Celtic knots are an ancient art form often attributed to Celtic cultures, used to decorate monuments and manuscripts, and to symbolise eternity and interconnectedness. This paper describes the framework CelticGraph to draw graphs as Celtic knots and links. The drawing process raises interesting combinatorial concepts in the theory of circuits in planar graphs. Further, CelticGraph uses a novel algorithm to represent edges as Bézier curves, aiming to show each link as a smooth curve with limited curvature.
For the entire collection see [Zbl 1539.68006].
For the entire collection see [Zbl 1539.68006].
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
References:
| [1] | Abello, J.; Gansner, E.; Lucchesi, CL; Moura, AV, Short and smooth polygonal paths, LATIN’98: Theoretical Informatics, 151-162, 1998, Heidelberg: Springer, Heidelberg · Zbl 1508.68382 · doi:10.1007/BFb0054318 |
| [2] | Bain, G., Celtic Art: The Methods of Construction, 1973, Mineola: Dover Publications, Mineola |
| [3] | Bain, I.: Celtic Knotwork. Sterling Publishing Co., New York (1986) |
| [4] | Blender Online Community: Blender - a 3D modelling and rendering package. Blender Foundation (2018). http://www.blender.org |
| [5] | Brandes, U.; Shubina, G.; Tamassia, R.; de Leeuw, WC; van Liere, R., Improving angular resolution in visualizations of geographic networks, Data Visualization 2000, 23-32, 2000, Eurographics: Springer, Eurographics · doi:10.1007/978-3-7091-6783-0_3 |
| [6] | Brandes, U.; Wagner, D., Using graph layout to visualize train interconnection data, J. Graph Algor. Appl., 4, 135-155, 2000 · Zbl 0953.68114 · doi:10.7155/jgaa.00028 |
| [7] | Clark, H., A Short and Easy Introduction to Heraldry, 1827, London: Printed for H. Washbourn, London |
| [8] | Devroye, L.; Kruszewski, P.; Brandenburg, FJ, The botanical beauty of random binary trees, Graph Drawing, 166-177, 1996, Heidelberg: Springer, Heidelberg · doi:10.1007/BFb0021801 |
| [9] | Di Battista, G.; Eades, P.; Tamassia, R.; Tollis, IG, Graph Drawing: Algorithms for the Visualization of Graphs, 1999, Upper Saddle River: Prentice Hall, Upper Saddle River · Zbl 1057.68653 |
| [10] | Duncan, CA; Eppstein, D.; Goodrich, MT; Kobourov, SG; Nöllenburg, M.; Brandes, U.; Cornelsen, S., Lombardi drawings of graphs, Graph Drawing, 195-207, 2011, Heidelberg: Springer, Heidelberg · Zbl 1314.68227 · doi:10.1007/978-3-642-18469-7_18 |
| [11] | Eades, P., Gröne, N., Klein, K., Eades, P., Schreiber, L., Schreiber, F.: Celticgraph: drawing graphs as celtic knots and links (2023) |
| [12] | Eades, P., Hong, S.H., McGrane, M., Meidiana, A.: GDot-i: interactive system for dot paintings of graphs. In: Krone, M., Lenti, S., Schmidt, J. (eds.) EuroVis 2022 - Posters. The Eurographics Association (2022) |
| [13] | Even-Zohar, C., Hass, J., Linial, N., Nowik, T.: Universal knot diagrams. J. Knot Theory Ramifications 28(07), 1950031 (2019) · Zbl 1440.57002 |
| [14] | Ferguson, R., An easier derivation of the curvature formula from first principles, Aust. Senior Math. J., 32, 16-22, 2018 |
| [15] | Fink, M.; Haverkort, H.; Nöllenburg, M.; Roberts, M.; Schuhmann, J.; Wolff, A.; Didimo, W.; Patrignani, M., Drawing metro maps using Bézier curves, Graph Drawing, 463-474, 2013, Heidelberg: Springer, Heidelberg · Zbl 1377.68274 · doi:10.1007/978-3-642-36763-2_41 |
| [16] | Finkel, B.; Tamassia, R.; Pach, J., Curvilinear graph drawing using the force-directed method, Graph Drawing, 448-453, 2005, Heidelberg: Springer, Heidelberg · doi:10.1007/978-3-540-31843-9_46 |
| [17] | Foley, JD; van Dam, A.; Feiner, S.; Hughes, JF, Computer Graphics - Principles and Practice, 1990, Boston: Addison-Wesley, Boston |
| [18] | Fries-Knoblach, J.: Die Kelten, pp. 138-142. Kohlhammer-Urban (2012) |
| [19] | Glassner, A., Celtic knotwork, part 1, IEEE Comput. Graph. Appl., 19, 5, 78-84, 1999 · doi:10.1109/38.788804 |
| [20] | Goodrich, MT; Wagner, CG; Whitesides, SH, A framework for drawing planar graphs with curves and polylines, Graph Drawing, 153-166, 1998, Heidelberg: Springer, Heidelberg · doi:10.1007/3-540-37623-2_12 |
| [21] | Graphviz. https://graphviz.org/ |
| [22] | Hong, S.H., Eades, P., Torkel, M.: Gdot: drawing graphs with dots and circles. In: 2021 IEEE 14th Pacific Visualization Symposium (PacificVis), pp. 156-165 (2021). doi:10.1109/PacificVis52677.2021.00029 |
| [23] | Irvine, V.; Biedl, T.; Kaplan, CS, Quasiperiodic bobbin lace patterns, J. Math. Arts, 14, 3, 177-198, 2020 · Zbl 1466.00025 · doi:10.1080/17513472.2020.1752999 |
| [24] | James, I.M.: History of Topology. North Holland (1999) · Zbl 0922.54003 |
| [25] | Junker, BH; Klukas, C.; Schreiber, F., VANTED: a system for advanced data analysis and visualization in the context of biological networks, BMC Bioinf., 7, 1, 1-13, 2006 · doi:10.1186/1471-2105-7-109 |
| [26] | Kindermann, P.; Kobourov, S.; Löffler, M.; Nöllenburg, M.; Schulz, A.; Vogtenhuber, B.; Frati, F.; Ma, K-L, Lombardi drawings of knots and links, Graph Drawing and Network Visualization, 113-126, 2018, Cham: Springer, Cham · Zbl 1464.68288 · doi:10.1007/978-3-319-73915-1_10 |
| [27] | Klempien-Hinrichs, R.; von Totth, C., Generation of celtic key patterns with tree-based collage grammars, Electron. Commun. Eur. Assoc. Softw. Sci. Technol., 26, 205-222, 2010 |
| [28] | Koffka, K.: Principles of Gestalt Psychology. Harcort Brace and Co., San Diego (1935) |
| [29] | Maier, B.: Die Geschichte, Kultur, Sprache, pp. 158-159. utb (2015) |
| [30] | Maier, B.: Die Geschichte, Kultur, Sprache, p. 159. utb (2015) |
| [31] | Müller, F.: Die Kunst der Kelten. C.H. Beck Wissen (2012) |
| [32] | Müller, F.: Die Kunst der Kelten, p. 119. C.H. Beck Wissen (2012) |
| [33] | Monks of St. Columba’s order of Iona: The Book of Kells. at the Old Library in Trinity College Dublin (9th century) |
| [34] | Murasugi, K.: Knot theory and its applications (1993) · Zbl 0817.57004 |
| [35] | Nishizeki, T., Rahman, M.S.: Planar graph drawing, Lecture Notes Series on Computing, vol. 12. World Scientific (2004) · Zbl 1070.68124 |
| [36] | Röber, R.: Exhibition catalogue Archäologisches Landesmuseum Stuttgart: Die Welt der Kelten. Zentren der Macht - Kostbarkeiten der Kunst, pp. 460-521. Jan Thorbecke Verlag (2012) |
| [37] | Röber, R.: Exhibition catalogue Archäologisches Landesmuseum Stuttgart: Die Welt der Kelten. Zentren der Macht - Kostbarkeiten der Kunst, pp. 512-515. Jan Thorbecke Verlag (2012) |
| [38] | Rieckhoff, S., Biel, J.: Die Kelten in Deutschland, pp. 197-206. Konrad Theiss Verlag (2001) |
| [39] | Rolland, T.; De Vico Fallani, F., Vizaj-a free online interactive software for visualizing spatial networks, PLoS ONE, 18, 3, 2023 · doi:10.1371/journal.pone.0282181 |
| [40] | Xu, K.; Rooney, C.; Passmore, P.; Ham, DH; Nguyen, PH, A user study on curved edges in graph visualization, IEEE Trans. Visual Comput. Graphics, 18, 12, 2449-2456, 2012 · doi:10.1109/TVCG.2012.189 |
| [41] | yworks. https://yWorks.org/ |
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.
