An annotated review on graph drawing and its applications. (English) Zbl 1533.05196
Summary: A drawing concerns the process of generating geometric representations of relational information, usually for visualization purposes. A good drawing provides an understanding of the system to the reader, while a poor drawing may create confusion. A lot of information related to graphs and graph drawings can be stored using data structures where vertices represent entities and edges correspond to relationships among entities. In this paper, we have reviewed various studies to present the unsolved problems in the domain of graph drawing and to identify its applications in real life. By reviewing the existing approaches related to graph drawings, we found that there exist various drawing strategies that efficiently allow us to create drawings with a confined area, relatively high angular resolution, user-restrained aspect ratio, a lesser number of bends, etc. Moreover, there are several known algorithms for addressing different measures of graph drawing (such as symmetricity, spirality, rotation, etc.) but they are usually restricted to specific sub-classes of planar graphs. The present study provides readers a better understanding of the field of graph drawing and related problems.
MSC:
| 05C62 | Graph representations (geometric and intersection representations, etc.) |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
References:
| [1] | Ackerman, E. (2014). A note on 1-planar graphs. Discrete Appl. Math. 175: 104-108. · Zbl 1298.05081 |
| [2] | Ackerman, E., Fulek, R., Tóth, C. D. (2012). Graphs that admit polyline drawings with few crossing angles. SIAM J. Discrete Math.26(1): 305-320. · Zbl 1245.05024 |
| [3] | Alam, M. J., Bekos, M. A., Kaufmann, M., Kindermann, P., Kobourov, S. G., Wolff, A. (2014). Smooth orthogonal drawings of planar graphs. In: Latin American Symposium on Theoretical Informatics, Berlin, Heidelberg: Springer, pp. 144-155. · Zbl 1405.68232 |
| [4] | Alam, M., Brandenburg, F. J., Kobourov, S. G. (2013). Straight-line grid drawings of 3-connected 1-planar graphs In: International Symposium on Graph Drawing, Cham: Springer, pp. 83-94. · Zbl 1406.68054 |
| [5] | Alegria, C., Da Lozzo, G., Di Battista, G., Frati, F., Grosso, F., Patrignani, M. (2022). Unit-length rectangular drawings of graphs. arXiv preprint arXiv:2208.14142. · Zbl 07727757 |
| [6] | Alfonso, X. (1843). King of Castile and León Libros del ajedrez, dados y tablas. |
| [7] | Anderson, J. A. (2006). Automata Theory with Modern Applications. Cambridge: Cambridge University Press. · Zbl 1127.68049 |
| [8] | Angelini, P. (2017). Monotone drawings of graphs with few directions. Inf. Process. Lett. 120: 16-22. · Zbl 1401.68241 |
| [9] | Angelini, P., Battista, G. D., Frati, F. (2013). Simultaneous embedding of embedded planar graphs. Int. J. Comput. Geom. Appl.23(02): 93-126. · Zbl 1344.68093 |
| [10] | Angelini, P., Bekos, M. A., Kaufmann, M., Pfister, M., Ueckerdt, T. (2018). Beyond-planarity: Turán-type results for non-planar bipartite graphs. In: 29th International Symposium on Algorithms and Computation (ISAAC 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. · Zbl 1535.05072 |
| [11] | Angelini, P., Colasante, E., Battista, G. D., Frati, F., Patrignani, M. (2010). Monotone drawings of graphs. In: International Symposium on Graph Drawing, Berlin, Heidelberg: Springer, pp. 13-24. · Zbl 1314.68208 |
| [12] | Angelini, P., Di Battista, G., Frati, F., Jelínek, V., Kratochvíl, J., Patrignani, M., Rutter, I. (2015). Testing planarity of partially embedded graphs. ACM Trans. Algorithms11(4): 1-42. · Zbl 1398.68385 |
| [13] | Angelini, P., Di Battista, G., Frati, F., Patrignani, M., Rutter, I. (2012). Testing the simultaneous embeddability of two graphs whose intersection is a biconnected or a connected graph. J. Discrete Algorithms14: 150-172. · Zbl 1247.05156 |
| [14] | Angelini, P., Didimo, W., Kobourov, S., Mchedlidze, T., Roselli, V., Symvonis, A., Wismath, S. (2015). Monotone drawings of graphs with fixed embedding. Algorithmica71(2): 233-257. · Zbl 1314.68209 |
| [15] | Angelini, P., Rutter, I., Sandhya, T. P. (2020). Extending partial orthogonal drawings In: International Symposium on Graph Drawing and Network Visualization, Cham: Springer, pp. 265-278. · Zbl 07436623 |
| [16] | Auber, D., Mary, P. (2007). Tulip: Data Visualization Software, Version 5.6.3. https://tulip.labri.fr/TulipDrupal/ |
| [17] | Auslander, L., Parter, S. V. (1961). On imbedding graphs in the sphere. Indiana Univ. Math. J.10(3): 517-523. · Zbl 0101.16704 |
| [18] | Bader, W. (1964). Das topologische Problem der gedruckten Schaltung und seine Lösung. Archiv f Elektrotechnik49(1): 2-12. |
| [19] | Ball, W. R. (1893). Mathematical recreations and essays. Bull. des Sci. Math. 17: 105-107. |
| [20] | Ball, W. W. R. (1914). Mathematical Recreations and Essays. London: Macmillan. · JFM 45.0371.03 |
| [21] | Barth, L., Niedermann, B., Rutter, I., Wolf, M. (2017). Towards a topology-shape-metrics framework for orthoradial drawings. In: 33rd International Symposium on Computational Geometry (SoCG 2017), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. · Zbl 1432.68334 |
| [22] | Battista, G. D., Eades, P., Tamassia, R., Tollis, I. G. (1998). Graph Drawing: Algorithms for the Visualization of Graphs. Hoboken, NJ: Prentice Hall PTR. · Zbl 1057.68653 |
| [23] | Bekos, M. A., Binucci, C., Battista, G. D., Didimo, W., Gronemann, M., Klein, K., Patrignani, M., Rutter, I. (2020). On turn-regular orthogonal representations. In: International Symposium on Graph Drawing and Network Visualization, Cham: Springer, pp. 250-264. · Zbl 07436622 |
| [24] | Bekos, M. A., Didimo, W., Liotta, G., Mehrabi, S., Montecchiani, F. (2017). On RAC drawings of 1-planar graphs. Theoret. Comput. Sci. 689: 48-57. · Zbl 1372.68202 |
| [25] | Bekos, M. A., Dijk, T. C. V., Kindermann, P., Wolff, A. (2015). Simultaneous drawing of planar graphs with right-angle crossings and few bends In: International Workshop on Algorithms and Computation, Cham: Springer, pp. 222-233. · Zbl 1432.68337 |
| [26] | Bekos, M. A., Kaufmann, M., Kobourov, S. G., Symvonis, A. (2012). Smooth orthogonal layouts. In: International Symposium on Graph Drawing, Berlin, Heidelberg: Springer, pp. 150-161. · Zbl 1377.68163 |
| [27] | Bertolazzi, P., Di Battista, G., Didimo, W. (2000). Computing orthogonal drawings with the minimum number of bends. IEEE Trans. Comput.49(8): 826-840. · Zbl 1392.68425 |
| [28] | Bhasker, J., Sahni, S. (1988). A linear algorithm to find a rectangular dual of a planar triangulated graph. Algorithmica3(1-4): 247-278. · Zbl 0635.68074 |
| [29] | Bhatia, S., Lad, K., Kumar, R. (2018). Bend-optimal orthogonal drawings of triconnected plane graphs. AKCE Int. J. Graphs Comb. 15(2): 168-173. · Zbl 1403.05103 |
| [30] | Biedl, T., Kant, G. (1998). A better heuristic for orthogonal graph drawings. Comput. Geom. 9(3): 159-180. · Zbl 0894.68104 |
| [31] | Biedl, T., Schmidt, J. M. (2015). Small-area orthogonal drawings of 3-connected graphs. In: International Symposium on Graph Drawing, Cham: Springer, pp. 153-165. · Zbl 1471.68185 |
| [32] | Biggs, N., Lloyd, E. K., Wilson, R. J. (1986). Graph Theory. Oxford: Oxford University Press, pp. 1736-1936. |
| [33] | Biofabric, Version 2 Beta Release 2 (2019). Available at: http://www.biofabric.org/ |
| [34] | Bläsius, T., Krug, M., Rutter, I., Wagner, D. (2010). Orthogonal graph drawing with flexibility constraints In: International Symposium on Graph Drawing, Berlin, Heidelberg: Springer, pp. 92-104. · Zbl 1314.68218 |
| [35] | Bläsius, T., Radermacher, M., Rutter, I. (2017). How to draw a planarization. In: International Conference on Current Trends in Theory and Practice of Informatics, Cham: Springer, pp. 295-308. · Zbl 1445.68150 |
| [36] | Bondy, J. A., Murty, U. S., eds. (1984). Progress in Graph Theory, Vol. 2. Toronto; Orlando: Academic Press. · Zbl 0546.00007 |
| [37] | Bonichon, N., Felsner, S., Mosbah, M. (2007). Convex drawings of 3-connected plane graphs. Algorithmica47(4): 399-420. · Zbl 1118.68100 |
| [38] | Bonichon, N., Saëc, B. L., Mosbah, M. (2002). Optimal area algorithm for planar polyline drawings. In: International Workshop on Graph-Theoretic Concepts in Computer Science, Berlin, Heidelberg: Springer, pp. 35-46. · Zbl 1022.68593 |
| [39] | Booth, K. S., Lueker, G. S. (1976). Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci. 13(3): 335-379. · Zbl 0367.68034 |
| [40] | Boyer, J. M., Myrvold, W. J. (1999). Stop minding your p’s and q’s: A simplified O (n) planar embedding algorithm. In: SODA, pp. 140-146. · Zbl 0938.68064 |
| [41] | Boyer, J. M., Myrvold, W. J. (2006). o (n) planarity by edge addition. Graph Algorithms Appl. 5: 241. Simplified · Zbl 1086.05067 |
| [42] | Brandes, U., Wagner, D. (2000). Using graph layout to visualize train interconnection data. J. Graph Algorithms Appl. 4(3): 135-155. · Zbl 0953.68114 |
| [43] | Brown, A. C. (1864). XLIV.On the theory of isomeric compounds. Trans. R Soc. Edinb. 23(3): 707-719. |
| [44] | Bruckdorfer, T., Kaufmann, M., Montecchiani, F. (2014). 1-Bend orthogonal partial edge drawing. J. Graph Algorithms Appl. 18(1): 111-131. · Zbl 1284.05271 |
| [45] | Cayley, A. (1857). XXVIII. On the theory of the analytical forms called trees. Lond. Edinb. Dublin Philos. Mag. J. Sci. 13(85): 172-176. |
| [46] | Chang, Y. J., Yen, H. C. (2017). On bend-minimized orthogonal drawings of planar 3-graphs. In: 33rd International Symposium on Computational Geometry (SoCG 2017), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. · Zbl 1432.68345 |
| [47] | Cheng, C. C., Duncan, C. A., Goodrich, M. T., Kobourov, S. G. (2001). Drawing planar graphs with circular arcs. Discrete Comput. Geom. 25(3): 405-418. · Zbl 0983.05060 |
| [48] | Chernobelskiy, R., Cunningham, K. I., Goodrich, M. T., Kobourov, S. G., Trott, L. (2011). Force-directed Lombardi-style graph drawing. In: International Symposium on Graph Drawing, Berlin, Heidelberg: Springer, pp. 320-331. · Zbl 1311.68165 |
| [49] | Chiba, N. (1984). Linear algorithms for convex drawings of planar graphs. Progress in graph theory. |
| [50] | Chiba, N., Nishizeki, T., Abe, S., Ozawa, T. (1985). A linear algorithm for embedding planar graphs using PQ-trees. J. Comput. Syst. Sci. 30(1): 54-76. · Zbl 0605.68060 |
| [51] | Chiba, N., Onoguchi, K., Nishizeki, T. (1985). Drawing plane graphs nicely. Acta Inform. 22(2): 187-201. · Zbl 0545.68057 |
| [52] | Chrobak, M., Kant, G. (1997). Convex grid drawings of 3-connected planar graphs. Int. J. Comput. Geom. Appl.07(03): 211-223. |
| [53] | Chrobak, M., Nakano, S. I. (1998). Minimum-width grid drawings of plane graphs. Comput. Geom. 11(1): 29-54. · Zbl 0904.68177 |
| [54] | Chrobak, M., Payne, T. H. (1995). A linear-time algorithm for drawing a planar graph on a grid. Inf. Process. Lett. 54(4): 241-246. · Zbl 0875.68452 |
| [55] | Cornelsen, S., Karrenbauer, A. (2011). Accelerated bend minimization. In: International Symposium on Graph Drawing, Berlin, Heidelberg: Springer, pp. 111-122. · Zbl 1311.68109 |
| [56] | Davidson, R., Harel, D. (1996). Drawing graphs nicely using simulated annealing. ACM Trans. Graph.15(4): 301-331. |
| [57] | De Fraysseix, H., de Mendez, P. O. (2001). Pigale Software. Available at: https://www.swmath.org/software/5435. |
| [58] | de Fraysseix, H., de Mendez, P. O. (2002). PIGALE-public implementation of a graph algorithm library and editor. SourceForge project page http://sourceforge.net/projects/pigale. |
| [59] | De Fraysseix, H. (2008). Trémaux trees and planarity. Electron. Notes Discrete Math. 31: 169-180. · Zbl 1267.05063 |
| [60] | De Fraysseix, H., De Mendez, P. O., Rosenstiehl, P. (2006). Trémaux trees and planarity. Int. J. Found. Comput. Sci.17(05): 1017-1029. · Zbl 1100.68076 |
| [61] | De Fraysseix, H., Pach, J., Pollack, R. (1990). How to draw a planar graph on a grid. Combinatorica10(1): 41-51. · Zbl 0728.05016 |
| [62] | Di Battista, G., Eades, P., Tamassia, R., Tollis, I. G. (1994). Algorithms for drawing graphs: an annotated bibliography. Comput. Geom.4(5): 235-282. · Zbl 0804.68001 |
| [63] | Di Battista, G., Liotta, G., Vargiu, F. (1998). Spirality and optimal orthogonal drawings. SIAM J. Comput.27(6): 1764-1811. · Zbl 0910.05061 |
| [64] | Di Giacomo, E., Liotta, G. (2007). Simultaneous embedding of outerplanar graphs, paths, and cycles. Int. J. Comput. Geom. Appl.17(02): 139-160. · Zbl 1116.05022 |
| [65] | Di Giacomo, E., Didimo, W., Liotta, G., Wismath, S. K. (2005). Curve-constrained drawings of planar graphs. Comput. Geom. 30(1): 1-23. · Zbl 1066.65026 |
| [66] | Di Giacomo, E., Didimo, W., Liotta, G., Wismath, S. K. (2006). Book embeddability of seriesparallel digraphs. Algorithmica45(4): 531-547. · Zbl 1099.68075 |
| [67] | Di Giacomo, E., Eades, P., Liotta, G., Meijer, H., Montecchiani, F. (2020). Polyline drawings with topological constraints. Theoret. Comput. Sci. 809: 250-264. · Zbl 1436.68232 |
| [68] | Dickerson, M., Eppstein, D., Goodrich, M. T., Meng, J. Y. (2003). Confluent drawings: Visualizing non-planar diagrams in a planar way. In: International Symposium on Graph Drawing, Berlin, Heidelberg: Springer, pp. 1-12. · Zbl 1215.68177 |
| [69] | Didimo, W., Kaufmann, M., Liotta, G., Ortali, G. (2022). Computing Bend-Minimum Orthogonal Drawings of Plane Series-Parallel Graphs in Linear Time. arXiv preprint arXiv:2205.07500. · Zbl 07742466 |
| [70] | Didimo, W., Liotta, G., Montecchiani, F. (2019). A survey on graph drawing beyond planarity. ACM Comput. Surv.52(1): 1-37. |
| [71] | Didimo, W., Liotta, G., Patrignani, M. (2018). Bend-minimum orthogonal drawings in quadratic time. In: International Symposium on Graph Drawing and Network Visualization, Cham: Springer, pp. 481-494. · Zbl 1519.68188 |
| [72] | Didimo, W., Liotta, G., Ortali, G., Patrignani, M. (2020). Optimal orthogonal drawings of planar 3-graphs in linear time. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, , Society for Industrial and Applied Mathematics, 806-825. · Zbl 07304072 |
| [73] | Dujmovi, V., Eppstein, D., Suderman, M., Wood, D. R. (2007). Drawings of planar graphs with few slopes and segments. Comput. Geom. 38(3): 194-212. · Zbl 1129.65010 |
| [74] | Duncan, C. A., Kobourov, S. G. (2006). Polar coordinate drawing of planar graphs with good angular resolution. Graph Algorithms Appl. 4: 311-333. · Zbl 1068.68102 |
| [75] | Durocher, S., Mondal, D. (2014). Trade-offs in planar polyline drawings. In: International Symposium on Graph Drawing, Berlin, Heidelberg: Springer, pp. 306-318. · Zbl 1426.68207 |
| [76] | Durocher, S., Mondal, D. (2019). Drawing plane triangulations with few segments. Comput. Geom. 77: 27-39. · Zbl 1506.68070 |
| [77] | Eades, P. (1984). A heuristic for graph drawing. Congressus Numerantium42: 149-160. |
| [78] | Eades, P., Hong, S. H., Liotta, G., Katoh, N., Poon, S. H. (2015). Straight-line drawability of a planar graph plus an edge. In: Workshop on Algorithms and Data Structures, Cham: Springer, pp. 301-313. · Zbl 1444.68141 |
| [79] | Elliot, M. A. (2010). Elliott Avedon Virtual Museum of Games. Available at: https://healthy.uwaterloo.ca/museum/VirtualExhibits/rowgames/mill.html. |
| [80] | Erten, C., Kobourov, S. G. (2004). Simultaneous embedding of planar graphs with few bends. In: International Symposium on Graph Drawing, Berlin, Heidelberg: Springer, pp. 195-205. · Zbl 1111.68578 |
| [81] | Euler, L. (1741). Solutio problematis ad geometriam situs pertinentis. Commentarii academiae scientiarum Petropolitanae, pp. 128-140. |
| [82] | Fáry, I. (1948). On straight-line representation of planar graphs. Acta Sci. Math. 11: 229-233. · Zbl 0030.17902 |
| [83] | Finkel, B., Tamassia, R. (2004). Curvilinear graph drawing using the force-directed method. In: International Symposium on Graph Drawing, Berlin, Heidelberg: Springer, pp. 448-453. |
| [84] | Fisk, C. J., Caskey, D. L., West, L. E. (1967). ACCEL: Automated circuit card etching layout. Proc. IEEE55(11): 1971-1982. |
| [85] | Formann, M., Hagerup, T., Haralambides, J., Kaufmann, M., Leighton, F. T., Symvonis, A., Welzl, E., Woeginger, G. (1993). Drawing graphs in the plane with high resolution. SIAM J. Comput.22(5): 1035-1052. · Zbl 0797.05042 |
| [86] | Gajer, P., Kobourov, S. G. (2002). GRIP: Graph drawing with intelligent placement. J. Graph Algorithms Appl. 6(3): 203-224. · Zbl 1027.68099 |
| [87] | Gansner, E. R., Koren, Y., North, S. (2004). Graph drawing by stress majorization. In: International Symposium on Graph Drawing, Berlin, Heidelberg: Springer, pp. 239-250. · Zbl 1111.68580 |
| [88] | Garg, A., Tamassia, R. (1996). A new minimum cost flow algorithm with applications to graph drawing. In: International Symposium on Graph Drawing, Berlin, Heidelberg: Springer, pp. 201-216. |
| [89] | Gephi:The open graph viz platform, Version 0.9. Available at: https://gephi.org/ |
| [90] | Giacomo, E. D., Liotta, G., Montecchiani, F. (2014). The planar slope number of subcubic graphs. In: Latin American Symposium on Theoretical Informatics, Berlin, Heidelberg: Springer, pp. 132-143. · Zbl 1406.05023 |
| [91] | Goldstein, A. J. (1963). An efficient and constructive algorithm for testing whether a graph can be embedded in a plane. In: Graph and Combinatorics Conference, Contract No. NONR 1858-(21), Office of Naval Research Logistics Proj., Dept. of Mathematics, Princeton University, May 16-18. |
| [92] | Goodrich, M. T., Wagner, C. G. (2000). A framework for drawing planar graphs with curves and polylines. J. Algorithms37(2): 399-421. · Zbl 0964.68104 |
| [93] | Gutwenger, C, Mutzel, P. (1998). Planar polyline drawings with good angular resolution. In: International Symposium on Graph Drawing, Berlin, Heidelberg: Springer, pp. 167-182. |
| [94] | Hadany, R., Harel, D. (2001). A multi-scale algorithm for drawing graphs nicely. Discrete Appl. Math. 113(1): 3-21. · Zbl 0981.68122 |
| [95] | Haeupler, B., Tarjan, R. E. (2008). Planarity algorithms via PQ-trees. Electron. Notes Discrete Math. 31: 143-149. · Zbl 1267.05088 |
| [96] | Haeupler, B., Jampani, K. R., Lubiw, A. (2013). Testing simultaneous planarity when the common graph is 2-connected. J. Graph Algorithms Appl.17(3): 147-171. · Zbl 1261.05015 |
| [97] | Hagberg, A., Schult, D., Swart, P. (2004). NetworkX, network analysis in Python, Version 2.8.6. Available at: https://networkx.org/documentation/stable/tutorial.html |
| [98] | Hamilton, R. W. (1859). The icosian Game, instruction leaflet, A copy of the leaflet can be found in [16], pp. 32-35. |
| [99] | Harel, D., Koren, Y. (2002). A fast multi-scale method for drawing large graphs. J. Graph Algorithms Appl. 6(3): 179-202. · Zbl 1027.68100 |
| [100] | Harel, D., Sardas, M. (1998). An algorithm for straight-line drawing of planar graphs. Algorithmica20(2): 119-135. · Zbl 0895.68105 |
| [101] | Hasan, M., Rahman, M. (2019). No-bend orthogonal drawings and no-bend orthogonally convex drawings of planar graphs. In: International Computing and Combinatorics Conference, Cham: Springer, pp. 254-265. · Zbl 1534.68168 |
| [102] | Haüy, R. J. (1784). Essai d’une théorie sur la structure des crystaux: appliquée à plusieurs genres de substances crystallisées. Chez Gogué & Née de la Rochelle. |
| [103] | Hong, S. H., Eades, P., Liotta, G., Poon, S. H. (2012). Fárys theorem for 1-planar graphs. In: International Computing and Combinatorics Conference, Berlin, Heidelberg: Springer, pp. 335-346. · Zbl 1364.68308 |
| [104] | Hopcroft, J., Tarjan, R. (1974). efficient planarity testing. J. ACM21(4): 549-568. · Zbl 0307.68025 |
| [105] | Hopcroft, J. E., Tarjan, R. E. (1973). Dividing a graph into triconnected components. SIAM J. Comput.2(3): 135-158. · Zbl 0281.05111 |
| [106] | Hültenschmidt, G., Kindermann, P., Meulemans, W., Schulz, A. (2017). Drawing planar graphs with few geometric primitives. In: International Workshop on Graph-Theoretic Concepts in Computer Science, Cham: Springer, pp. 316-329. · Zbl 1483.05183 |
| [107] | Iqbal Hossain, M., Saidur Rahman, M. (2015). Good spanning trees in graph drawing. Theor. Comput. Sci. 607: 149-165. · Zbl 1332.68173 |
| [108] | Iqbal Hossain, M., Saidur Rahman, M. (2015). Straight-line monotone grid drawings of series parallel graphs. Discrete Math. Algorithm. Appl.07 (02): 1550007. · Zbl 1331.68153 |
| [109] | Jünger, M., Mutzel, P., Spisla, C. (2018). More compact orthogonal drawings by allowing additional bends. Information9(7): 153. |
| [110] | Kahng, A. B., Lienig, J., Markov, I. L., Hu, J. (2011). VLSI Physical Design: From Graph Partitioning to Timing Closure. Dordrecht: Springer. · Zbl 1213.68009 |
| [111] | Kant, G., He, X. (1997). Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems. Theor. Comput. Sci. 172(1-2): 175-193. · Zbl 0903.68137 |
| [112] | Kant, G. (1996). Drawing planar graphs using the canonical ordering. Algorithmica16(1): 4-32. · Zbl 0851.68086 |
| [113] | Kawaguchi, A., Nagamochi, H. (2007). Orthogonal drawings for plane graphs with specified face areas. In: International Conference on Theory and Applications of Models of Computation, Berlin, Heidelberg: Springer, pp. 584-594. · Zbl 1200.68171 |
| [114] | Kawaguchi, A., Nagamochi, H. (2009). Drawing slicing graphs with face areas. Theor. Comput. Sci. 410(11): 1061-1072. · Zbl 1162.68026 |
| [115] | Kindermann, P., Mchedlidze, T., Schneck, T., Symvonis, A. (2019). Drawing planar graphs with few segments on a polynomial grid. In: International Symposium on Graph Drawing and Network Visualization, Cham: Springer, pp. 416-429. · Zbl 1542.68153 |
| [116] | Kindermann, P., Schulz, A., Spoerhase, J., Wolff, A. (2014). On monotone drawings of trees. In: International Symposium on Graph Drawing, Berlin, Heidelberg: Springer, pp. 488-500. · Zbl 1405.68249 |
| [117] | Klose, P. (2012). A Generic Framework for the Topology-Shapemetrics Based Layout. Christian-Albrechts-Universität zu Kiel. |
| [118] | Kobourov, S. G., Wampler, K. (2005). Non-Euclidean spring embedders. IEEE Trans. Vis. Comput. Graph. 11(6): 757-767. |
| [119] | Kosak, C. (1991). A parallel genetic algorithm for network-diagram layout. In: Proceedings of the Fourth International Conference on Genetic Algorithms, , 458-465. |
| [120] | Koźmiński, K., Kinnen, E. (1985). Rectangular duals of planar graphs. Networks15(2): 145-157. · Zbl 0585.05029 |
| [121] | Kruja, E., Marks, J., Blair, A., Waters, R. (2001). A short note on the history of graph drawing. In: International Symposium on Graph Drawing, Berlin, Heidelberg: Springer, pp. 272-286. · Zbl 1054.68500 |
| [122] | Kruskal, J. B. (1980). Designing network diagrams. In: Proc. 1st General Conference on Social Graphics, US Dept. of the Census, , 22-50. |
| [123] | Kuratowski, C. (1930). Sur le probleme des courbes gauches en topologie. Fund. Math.15(1): 271-283. · JFM 56.1141.03 |
| [124] | Lai, Y. T., Leinwand, S. M. (1990). A theory of rectangular dual graphs. Algorithmica5(1-4): 467-483. · Zbl 0712.05053 |
| [125] | Leighton, F. T. (1984). New lower bound techniques for VLSI. Math. Systems Theory17(1): 47-70. · Zbl 0488.94048 |
| [126] | Leiserson, C. E. (1980). Area-efficient graph layouts. In: 21st Annual Symposium on Foundations of Computer Science (SFCS 1980), IEEE, pp. 270-281. |
| [127] | Lempel, A. (1967). An algorithm for planarity testing of graphs. In: Rosenstiel, P., ed. Theory of Graphs, International Symposium, Rome, July 1966. · Zbl 0197.50204 |
| [128] | Listing, J. B. (1848). Vorstudien zur topologie. Vandenhoeck und Ruprecht. |
| [129] | Low, G. (2004). Graphviz: Graph visualization software. Available at: https://graphviz.org/ |
| [130] | Mehlhorn, K., Mutzel, P. (1996). On the embedding phase of the Hopcroft and Tarjan planarity testing algorithm. Algorithmica16(2): 233-242. · Zbl 0854.68075 |
| [131] | Miura, K., Haga, H., Nishizeki, T. (2006). Inner rectangular drawings of plane graphs. Int. J. Comput. Geom. Appl.16(02n03): 249-270. · Zbl 1097.65038 |
| [132] | Mondal, D., Nishat, R. I., Biswas, S., Rahman, M. (2013). Minimum-segment convex drawings of 3-connected cubic plane graphs. J. Comb. Optim. 25(3): 460-480. · Zbl 1271.90071 |
| [133] | Mondal, D., Nishat, R. I., Rahman, M. S., Alam, M. J. (2011). Minimum-area drawings of plane 3-trees. · Zbl 1217.05074 |
| [134] | Nakano, S. I., Yoshikawa, M. (2000). A linear-time algorithm for bend-optimal orthogonal drawings of biconnected cubic plane graphs. In: International Symposium on Graph Drawing, Berlin, Heidelberg: Springer, pp. 296-307. · Zbl 1043.68631 |
| [135] | Nees, E., Ludo, W. Visualizing scientific landscapes. Available at: https://www.vosviewer.com/ |
| [136] | Niedermann, B., Rutter, I. (2020). An integer-linear program for bend-minimization in ortho-radial drawings. In: International Symposium on Graph Drawing and Network Visualization, Cham: Springer, pp. 235-249. · Zbl 07436621 |
| [137] | Nishizeki, T., Rahman, M. S. (2004). Planar Graph Drawing, Vol. 12. Singapore: World Scientific. · Zbl 1070.68124 |
| [138] | Nöllenburg, M. (2020). Crossing layout in non-planar graph drawings. In: Hong, S.-H., Tokuyama, T., eds. Beyond Planar Graphs. Singapore: Springer, pp. 187-209. · Zbl 07374192 |
| [139] | Omran, N. F., Abd-el Ghany, S. F. (2015). Applying topology-shape-metric and fuzzy genetic algorithm for automatic planar hierarchical and orthogonal graphs. Int. J. Adv. Comput. Sci. Appl. 6(5): 81-87. |
| [140] | Ono, K. (2001). Cytoscape: Open source software, network data integration, analysis, and visualization in a box. Available at: https://cytoscape.org/ |
| [141] | Ontrup, J., Ritter, H. (2001). Hyperbolic self-organizing maps for semantic navigation. In: Advances in Neural Information Processing Systems, Vol. 14. · Zbl 1009.68815 |
| [143] | Papakostas, A., Tollis, I. G. (1998). Algorithms for area-efficient orthogonal drawings. Comput. Geom. 9(1-2): 83-110. · Zbl 0894.68102 |
| [144] | Peixoto, T. D. P. (2006). Graph-tool. Available at: https://graph-tool.skewed.de/ |
| [145] | Quinn, N., Breuer, M. (1979). A forced directed component placement procedure for printed circuit boards. IEEE Trans. Circuits Syst.26(6): 377-388. · Zbl 0409.94053 |
| [146] | Rahman, M., Nishizeki, T. (2002). Bend-minimum orthogonal drawings of plane 3-graphs. In: International Workshop on Graph-Theoretic Concepts in Computer Science, Berlin, Heidelberg: Springer, pp. 367-378. · Zbl 1022.68603 |
| [147] | Rahman, M. S., Egi, N., Nishizeki, T. (2005). No-bend orthogonal drawings of subdivisions of planar triconnected cubic graphs. IEICE Trans. Inf. Syst. E88-D(1): 23-30. · Zbl 1215.05120 |
| [148] | Rahman, M. S., Miura, K., Nishizeki, T. (2009). Octagonal drawings of plane graphs with prescribed face areas. Comput. Geom. 42(3): 214-230. · Zbl 1226.05103 |
| [149] | Rahman, M. S., Nakano, S. I., Nishizeki, T. (1998). Rectangular grid drawings of plane graphs. Comput. Geom. 10(3): 203-220. · Zbl 0901.68202 |
| [150] | Rahman, M. S., Nakano, S. I., Nishizeki, T. (2002). A linear algorithm for bend-optimal orthogonal drawings of triconnected cubic plane graphs. In: Graph Algorithms and ApplicationsI, pp. 343-374. · Zbl 0946.05078 |
| [151] | Rahman, M. S., Nakano, S. I., Nishizeki, T. (2002). Rectangular drawings of plane graphs without designated corners. Comput. Geom. 21(3): 121-138. · Zbl 0993.68131 |
| [152] | Rahman, M. S., Nishizeki, T., Ghosh, S. (2004). Rectangular drawings of planar graphs. J. Algorithms50(1): 62-78. · Zbl 1075.68065 |
| [153] | Rahman, M. S., Nishizeki, T., Naznin, M. (2006). Orthogonal drawings of plane graphs without bends. Graph Algorithms Appl. 4: 335-362. · Zbl 1068.68106 |
| [154] | Roth, J., Hashimshony, R., Wachman, A. (1982). Turning a graph into a rectangular floor plan. Build. Environ.17(3): 163-173. |
| [155] | Schäffter, M. (1995). Drawing graphs on rectangular grids. Discrete Appl. Math. 63(1): 75-89. · Zbl 0853.05030 |
| [156] | Schmidt, J. M. (2013). A planarity test via construction sequences. In: International Symposium on Mathematical Foundations of Computer Science, Berlin, Heidelberg: Springer, pp. 765-776. · Zbl 1400.05064 |
| [157] | Schnyder, W. (1990). Embedding planar graphs on the grid. In: Proceedings of the first Annual ACM-SIAM Symposium on Discrete Algorithms, , 138-148. · Zbl 0786.05029 |
| [158] | Scott, J. (2000). Social Network Analysis: A Handbook, 2nd ed. London: SAGE Publications. |
| [159] | Seifert, E., Rademacher, H. (1934). Vorlesungen über die Theorie der Polyeder (Die Grundlehren d. math. Wiss. in Einzeldarstell. mit besonderer Berücksichtigung d. Anwendungsgeb. Hrsg. von R. Courant. Gemeinsam mit W. Blaschke, M. Born u. BL van der Waerden. Bd. 41.) Berlin 1934, Julius Springer Verlag. XII+ 351 S. Preis geb. 27 M, geb. 28, 80 M. · Zbl 0009.36503 |
| [160] | Shih, W. K., Hsu, W. L. (1999). A new planarity test. Theor. Comput. Sci. 223(1): 179-192. · Zbl 0930.05092 |
| [161] | Simonetto, P., Archambault, D., Auber, D., Bourqui, R. (2011). ImPrEd: An improved force directed algorithm that prevents nodes from crossing edges. Computer Graphics Forum, Oxford30(3): 1071-1080. |
| [162] | Stein, S. K. (1951). Convex maps. Proc. Amer. Math. Soc.2(3): 464-466. · Zbl 0042.42004 |
| [163] | Sugiyama, K. (2002). Graph Drawing and Applications for Software and Knowledge Engineers, Vol. 11. Singapore: World Scientific. · Zbl 1011.68068 |
| [164] | Tamassia, R., Tollis, I. G. (1989). Planar grid embedding in linear time. IEEE Trans. Circuits Syst.36(9): 1230-1234. |
| [165] | Tamassia, R. (1987). On embedding a graph in the grid with the minimum number of bends. SIAM J. Comput.16(3): 421-444. · Zbl 0654.68090 |
| [166] | Tamassia, R., ed. (2013). Handbook of Graph Drawing and Visualization. Boca Raton, FL: CRC Press. · Zbl 1275.68033 |
| [167] | Tutte, W. T. (1960). Convex representations of graphs. Proc. London Math. Soc. s3-10(1): 304-320. · Zbl 0094.36301 |
| [168] | Tutte, W. T. (1963). How to draw a graph. Proc. London Math. Soc. s3-13(1): 743-767. · Zbl 0115.40805 |
| [169] | Upasani, N., Shekhawat, K., Sachdeva, G. (2020). Automated generation of dimensioned rectangular floorplans. Autom. Constr. 113: 103149. |
| [170] | Valiant, L. G. (1981). Universality considerations in VLSI circuits. IEEE Trans. Comput. C-30(2): 135-140. · Zbl 0455.94046 |
| [171] | Wagner, K. (1936). Bemerkungen zum vierfarbenproblem. Jahresbericht Der Deutschen Mathematiker-Vereinigung46: 26-32. · JFM 62.0656.02 |
| [172] | Wagner, K. (1937). Uber eine Erweiterung eines Satzes von Kuratowski, Deutsche Math. · Zbl 0016.37602 |
| [173] | Wagner, K. (1937). Über eine Eigenschaft der ebenen Komplexe. Math. Ann.114(1): 570-590. · JFM 63.0550.01 |
| [174] | Wikipedia Flowchart-Wikipedia, the Free Encyclopedia (2021). Available at: http://en.wikipedia.org/w/index.php?title=Flowchart{/&}oldid=1009218979. [Online; accessed 08-March-2021]. |
| [175] | Wolfram, S. (2009). Wolfram Mathematica Online: Bring Mathematica to Life in the Cloud. Available at: https://www.wolfram.com/mathematica/online/?src=google{/&}amp;420/ |
| [176] | Xu, T., Yang, J., Gou, G. (2018). A force-directed algorithm for drawing directed graphs symmetrically. Math. Probl. Eng. 2018: 1-24. · Zbl 1427.68256 |
| [178] | Zeijlemaker, S., Keijsper, J. C. M. (2018). Planarity testing. |
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.
