Drawing Non-Planar Graphs with Crossing-Free Subgraphs

Angelini, Patrizio and Binucci, Carla and Da Lozzo, Giordano and Didimo, Walter and Grilli, Luca and Montecchiani, Fabrizio and Patrignani, Maurizio and Tollis, Ioannis G. (2013) Drawing Non-Planar Graphs with Crossing-Free Subgraphs. In: 21st International Symposium, GD 2013, September 23-25, 2013, Bordeaux, France , pp. 292-303 (Official URL: http://dx.doi.org/10.1007/978-3-319-03841-4_26).

Full text not available from this repository.


We initiate the study of the following problem: Given a non-planar graph G and a planar subgraph S of G, does there exist a straight-line drawing Γ of G in the plane such that the edges of S are not crossed in Γ? We give positive and negative results for different kinds of spanning subgraphs S of G. Moreover, in order to enlarge the subset of instances that admit a solution, we consider the possibility of bending the edges of G ∖ S; in this setting different trade-offs between number of bends and drawing area are given.

Item Type:Conference Paper
Classifications:G Algorithms and Complexity > G.999 Others
P Styles > P.540 Planar
P Styles > P.720 Straight-line
ID Code:1383

Repository Staff Only: item control page


Ackerman, E.: On the maximum number of edges in topological graphs with no four pairwise crossing edges. Discrete & Computational Geometry 41(3), 365–375 (2009)

Ackerman, E., Tardos, G.: On the maximum number of edges in quasi-planar graphs. Journal of Combinatorial Theory, Ser. A 114(3), 563–571 (2007)

Angelini, P., Di Battista, G., Frati, F., Patrignani, M., Rutter, I.: Testing the simultaneous embeddability of two graphs whose intersection is a biconnected or a connected graph. Journal of Discrete Algorithms 14, 150–172 (2012)

Angelini, P., Binucci, C., Da Lozzo, G., Didimo, W., Grilli, L., Montecchiani, F., Patrignani, M., Tollis, I.G.: Drawings of non-planar graphs with crossing-free subgraphs. ArXiv e-prints 1308.6706 (September 2013)

Bárány, I., Rote, G.: Strictly convex drawings of planar graphs. Documenta. Math. 11, 369–391 (2006)

Blasiüs, T., Kobourov, S.G., Rutter, I.: Simultaneous embedding of planar graphs. In: Tamassia, R. (ed.) Handbook of Graph Drawing and Visualization. CRC Press (2013)

Brandenburg, F.J., Eppstein, D., Gleißner, A., Goodrich, M.T., Hanauer, K., Reislhuber, J.: On the density of maximal 1-planar graphs. In: Didimo, W., Patrignani, M. (eds.) GD 2012. LNCS, vol. 7704, pp. 327–338. Springer, Heidelberg (2013)

Buchheim, C., Chimani, M., Gutwenger, C., Jünger, M., Mutzel, P.: Crossings and planarization. In: Tamassia, R. (ed.) Handbook of Graph Drawing and Visualization. CRC Press (2013)

Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing. Prentice Hall, Upper Saddle River (1999)

Di Giacomo, E., Didimo, W., Liotta, G., Montecchiani, F.: h-quasi planar drawings of bounded treewidth graphs in linear area. In: Golumbic, M.C., Stern, M., Levy, A., Morgenstern, G. (eds.) WG 2012. LNCS, vol. 7551, pp. 91–102. Springer, Heidelberg (2012)

Di Giacomo, E., Didimo, W., Liotta, G., Montecchiani, F.: Area requirement of graph drawings with few crossings per edge. Computational Geometry 46(8), 909–916 (2013)

Didimo, W.: Density of straight-line 1-planar graph drawings. Information Processing Letters 113(7), 236–240 (2013)

Didimo, W., Eades, P., Liotta, G.: Drawing graphs with right angle crossings. Theoretical Computer Science 412(39), 5156–5166 (2011)

Didimo, W., Liotta, G.: The crossing angle resolution in graph drawing. In: Pach, J. (ed.) Thirty Essays on Geometric Graph Theory. Springer (2013)

Eades, P., Hong, S.H., Katoh, N., Liotta, G., Schweitzer, P., Suzuki, Y.: Testing maximal 1-planarity of graphs with a rotation system in linear time - (extended abstract). In: Didimo, W., Patrignani, M. (eds.) GD 2012. LNCS, vol. 7704, pp. 339–345. Springer, Heidelberg (2013)

Hong, S.-H., Eades, P., Liotta, G., Poon, S.-H.: Fáry’s theorem for 1-planar graphs. In: Gudmundsson, J., Mestre, J., Viglas, T. (eds.) COCOON 2012. LNCS, vol. 7434, pp. 335–346. Springer, Heidelberg (2012)

Jansen, K., Woeginger, G.J.: The complexity of detecting crossingfree configurations in the plane. BIT Numerical Mathematics 33(4), 580–595 (1993)

Kant, G.: Drawing planar graphs using the canonical ordering. Algorithmica 16(1), 4–32 (1996)

Knauer, C., Schramm, É., Spillner, A., Wolff, A.: Configurations with few crossings in topological graphs. Computational Geometry 37(2), 104–114 (2007)

Korzhik, V.P., Mohar, B.: Minimal obstructions for 1-immersions and hardness of 1-planarity testing. Journal of Graph Theory 72(1), 30–71 (2013)

Kowalik, L., Kurowski, M.: Short path queries in planar graphs in constant time. In: Larmore, L.L., Goemans, M.X. (eds.) STOC 2003, pp. 143–148. ACM (2003)

Kratochvìl, J., Lubiv, A., Nešetřil, J.: Noncrossing subgraphs in topological layouts. SIAM Journal on Discrete Mathematics 4(2), 223–244 (1991)

Pach, J., Shahrokhi, F., Szegedy, M.: Applications of the crossing number. Algorithmica 16(1), 111–117 (1996)

Pach, J., Tóth, G.: Graphs drawn with few crossings per edge. Combinatorica 17(3), 427–439 (1997)

Rivera-Campo, E., Urrutia-Galicia, V.: A sufficient condition for the existence of plane spanning trees on geometric graphs. Computational Geometry 46(1), 1–6 (2013)

Suk, A.: k-quasi-planar graphs. In: Speckmann, B. (ed.) GD 2011. LNCS, vol. 7034, pp. 266–277. Springer, Heidelberg (2011)

Tutte, W.T.: How to draw a graph. Proceedings of the London Mathematical Society s3-13(1), 743–767 (1963)

Valtr, P.: On geometric graphs with no k pairwise parallel edges. Discrete & Computational Geometry 19(3), 461–469 (1998)