×

Large angle crossing drawings of planar graphs in subquadratic area. (English) Zbl 1374.68348

Márquez, Alberto (ed.) et al., Computational geometry. XIV Spanish meeting on computational geometry, EGC 2011, dedicated to Ferran Hurtado on the occasion of his 60th birthday, Alcalá de Henares, Spain, June 27–30, 2011. Revised selected papers. Berlin: Springer (ISBN 978-3-642-34190-8/pbk). Lecture Notes in Computer Science 7579, 200-209 (2012).
Summary: This paper describes algorithms for computing non-planar drawings of planar graphs in subquadratic area such that: (i) edge crossings are allowed only if they create large angles; (ii) the maximum number of bends per edge is bounded by a (small) constant.
For the entire collection see [Zbl 1253.68016].

MSC:

68R10 Graph theory (including graph drawing) in computer science
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ackerman, E., Fulek, R., Tóth, C.D.: Graphs that admit polyline drawings with few crossing angles. SIAM Journal on Discrete Mathematics 26(1), 305–320 (2012) · Zbl 1245.05024 · doi:10.1137/100819564
[2] Angelini, P., Cittadini, L., Di Battista, G., Didimo, W., Frati, F., Kaufmann, M., Symvonis, A.: On the perspectives opened by right angle crossing drawings. Journal of Graph Algorithms and Applications 15(1), 53–78 (2011) · Zbl 1217.05063 · doi:10.7155/jgaa.00217
[3] Argyriou, E.N., Bekos, M.A., Symvonis, A.: The Straight-Line RAC Drawing Problem Is NP-Hard. In: Černá, I., Gyimóthy, T., Hromkovič, J., Jefferey, K., Králović, R., Vukolić, M., Wolf, S. (eds.) SOFSEM 2011. LNCS, vol. 6543, pp. 74–85. Springer, Heidelberg (2011) · Zbl 1298.68198 · doi:10.1007/978-3-642-18381-2_6
[4] Arikushi, K., Fulek, R., Keszegh, B., Moric, F., Tóth, C.D.: Graphs that admit right angle crossing drawings. Computational Geometry: Theory & Applications 45(4), 169–177 (2012) · Zbl 1259.65035 · doi:10.1016/j.comgeo.2011.11.008
[5] Bonichon, N., Le Saëc, B., Mosbah, M.: Optimal Area Algorithm for Planar Polyline Drawings. In: Kučera, L. (ed.) WG 2002. LNCS, vol. 2573, pp. 35–46. Springer, Heidelberg (2002) · Zbl 1022.68593 · doi:10.1007/3-540-36379-3_4
[6] de Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica 10(1), 41–51 (1990) · Zbl 0728.05016 · doi:10.1007/BF02122694
[7] Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing. Prentice Hall, Upper Saddle River (1999) · Zbl 1057.68653
[8] Di Giacomo, E., Didimo, W., Liotta, G., Meijer, H.: Area, curve complexity, and crossing resolution of non-planar graph drawings. Theory of Computing Systems 49(3), 565–575 (2011) · Zbl 1252.68210 · doi:10.1007/s00224-010-9275-6
[9] Didimo, W., Eades, P., Liotta, G.: Drawing Graphs with Right Angle Crossings. In: Dehne, F., Gavrilova, M., Sack, J.-R., Tóth, C.D. (eds.) WADS 2009. LNCS, vol. 5664, pp. 206–217. Springer, Heidelberg (2009) · Zbl 1253.68332 · doi:10.1007/978-3-642-03367-4_19
[10] Didimo, W., Eades, P., Liotta, G.: Drawing graphs with right angle crossings. Theoretical Computer Science 412(39), 5156–5166 (2011) · Zbl 1225.68134 · doi:10.1016/j.tcs.2011.05.025
[11] Diestel, R.: Graph Theory. Springer, Heidelberg (2010) · Zbl 1204.05001 · doi:10.1007/978-3-642-14279-6
[12] Diks, K., Djidjev, H., Sýkora, O., Vrto, I.: Edge separators of planar and outerplanar graphs with applications. J. Algorithms 14(2), 258–279 (1993) · Zbl 0764.68112 · doi:10.1006/jagm.1993.1013
[13] Dujmović, V., Gudmundsson, J., Morin, P., Wolle, T.: Notes on large angle crossing graphs. Chicago Journal of Theoretical Computer Science, article 4, 1–14 (2011) · Zbl 1286.05034 · doi:10.4086/cjtcs.2011.004
[14] Frati, F., Patrignani, M.: A Note on Minimum-Area Straight-Line Drawings of Planar Graphs. In: Hong, S.-H., Nishizeki, T., Quan, W. (eds.) GD 2007. LNCS, vol. 4875, pp. 339–344. Springer, Heidelberg (2008) · Zbl 1137.68489 · doi:10.1007/978-3-540-77537-9_33
[15] Huang, W.: Using eye tracking to investigate graph layout effects. In: Hong, S.H., Ma, K.L. (eds.) Asia-Pacific Symposium on Visualization (APVIS 2007), pp. 97–100. IEEE (2007) · doi:10.1109/APVIS.2007.329282
[16] Huang, W., Hong, S.H., Eades, P.: Effects of crossing angles. In: Pacific Visualization (PacificVis 2008), pp. 41–46. IEEE (2008) · doi:10.1109/PACIFICVIS.2008.4475457
[17] Kaufmann, M., Wagner, D. (eds.): Drawing Graphs. LNCS, vol. 2025. Springer, Heidelberg (2001) · Zbl 0977.68644
[18] Korach, E., Solel, N.: Tree-width, path-widt, and cutwidth. Discrete Applied Mathematics 43(1), 97–101 (1993) · Zbl 0788.05057 · doi:10.1016/0166-218X(93)90171-J
[19] Schnyder, W.: Embedding planar graphs on the grid. In: Symposium on Discrete Algorithms (SODA 1990), pp. 138–148 (1990) · Zbl 0786.05029
[20] Tamassia, R., Tollis, I.G.: A unified approach to visibility representation of planar graphs. Discrete & Computational Geometry 1, 321–341 (1986) · Zbl 0607.05026 · doi:10.1007/BF02187705
[21] Tamassia, R., Tollis, I.G.: Planar bookgrid embedding in linear time. IEEE Transactions on Cyrcuits and Systems 36(9), 1230–1234 (1989) · doi:10.1109/31.34669
[22] Valiant, L.G.: Universality considerations in VLSI circuits. IEEE Transactions on Computers 30(2), 135–140 (1981) · Zbl 0455.94046 · doi:10.1109/TC.1981.6312176
[23] Wood, D.R.: Grid drawings of k-colourable graphs. Computational Geometry: Theory & Applications 30(1), 25–28 (2005) · Zbl 1065.65043 · doi:10.1016/j.comgeo.2004.06.001
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.