Fan-Planar Graphs: Combinatorial Properties and Complexity Results

Binucci, Carla and Di Giacomo, Emilio and Didimo, Walter and Montecchiani, Fabrizio and Patrignani, Maurizio and Tollis, Ioannis G. (2014) Fan-Planar Graphs: Combinatorial Properties and Complexity Results. In: Graph Drawing 22nd International Symposium, GD 2014, September 24-26, 2014, Würzburg, Germany , pp. 186-197 (Official URL: http://dx.doi.org/10.1007/978-3-662-45803-7_16).

Full text not available from this repository.

Abstract

In a fan-planar drawing of a graph an edge can cross only edges with a common end-vertex. Fan-planar drawings have been recently introduced by Kaufmann and Ueckerdt, who proved that every n-vertex fan-planar drawing has at most 5n − 10 edges, and that this bound is tight for n ≥ 20. We extend their result from both the combinatorial and the algorithmic point of view. We prove tight bounds on the density of constrained versions of fan-planar drawings and study the relationship between fan-planarity and k-planarity. Also, we prove that testing fan-planarity in the variable embedding setting is NP-complete.

Item Type:Conference Paper
Additional Information:10.1007/978-3-662-45803-7_16
Classifications:G Algorithms and Complexity > G.420 Crossings
P Styles > P.480 Layered
P Styles > P.540 Planar
P Styles > P.999 Others
Z Theory > Z.750 Topology
Z Theory > Z.999 Others
ID Code:1432

Repository Staff Only: item control page

References

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., Fulek, R., Tóth, C.D.: Graphs that admit polyline drawings with few crossing angles. SIAM J. on Discrete Mathematics 26(1), 305–320 (2012)

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

Agarwal, P.K., Aronov, B., Pach, J., Pollack, R., Sharir, M.: Quasi-planar graphs have a linear number of edges. Combinatorica 17(1), 1–9 (1997)

Alam, M.J., Brandenburg, F.J., Kobourov, S.G.: Straight-line grid drawings of 3-connected 1-planar graphs. In: Wismath, S., Wolff, A. (eds.) GD 2013. LNCS, vol. 8242, pp. 83–94. Springer, Heidelberg (2013)

Angelini, P., Di Battista, G., Didimo, W., Frati, F., Hong, S.H., Kaufmann, M., Liotta, G., Lubiw, A.: Large angle crossing drawings of planar graphs in subquadratic area. In: Márquez, A., Ramos, P., Urrutia, J. (eds.) EGC 2011. LNCS, vol. 7579, pp. 200–209. Springer, Heidelberg (2012)

Asano, K.: The crossing number of K 1,3,n and K 2,3,n . J. of Graph Theory 10(1), 1–8 (1986)

Auer, C., Bachmaier, C., Brandenburg, F.J., Gleißner, A., Hanauer, K., Neuwirth, D., Reislhuber, J.: Recognizing outer 1-planar graphs in linear time. In: Wismath, S., Wolff, A. (eds.) GD 2013. LNCS, vol. 8242, pp. 107–118. Springer, Heidelberg (2013)

Auer, C., Brandenburg, F.J., Gleißner, A., Hanauer, K.: On sparse maximal 2-planar graphs. In: Didimo, W., Patrignani, M. (eds.) GD 2012. LNCS, vol. 7704, pp. 555–556. Springer, Heidelberg (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)

Cheong, O., Har-Peled, S., Kim, H., Kim, H.S.: On the number of edges of fan-crossing free graphs. In: Cai, L., Cheng, S.-W., Lam, T.-W. (eds.) ISAAC 2013. LNCS, vol. 8283, pp. 163–173. Springer, Heidelberg (2013)

Dehkordi, H.R., Eades, P.: Every outer-1-plane graph has a right angle crossing drawing. International J. on Computational Geometry and Appl. 22(6), 543–558 (2012)

Di Giacomo, E., Didimo, W., Eades, P., Liotta, G.: 2-layer right angle crossing drawings. Algorithmica 68(4), 954–997 (2014)

Di Giacomo, E., Didimo, W., Liotta, G., Meijer, H.: Area, curve complexity, and crossing resolution of non-planar graph drawings. Theory of Computing Syst. 49(3), 565–575 (2011)

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)

Dickerson, M., Eppstein, D., Goodrich, M.T., Meng, J.Y.: Confluent drawings: Visualizing non-planar diagrams in a planar way. J. of Graph Algorithms and Appl. 9(1), 31–52 (2005)

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. Theor. Comput. Sci. 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 (2012)

Dujmović, V., Gudmundsson, J., Morin, P., Wolle, T.: Notes on large angle crossing graphs. Chicago J. on Theoretical Computer Science 2011 (2011)

Eades, P., Liotta, G.: Right angle crossing graphs and 1-planarity. Discrete Applied Mathematics 161(7-8), 961–969 (2013)

Eppstein, D., Goodrich, M.T., Meng, J.Y.: Confluent layered drawings. Algorithmica 47(4), 439–452 (2007)

Fox, J., Pach, J., Suk, A.: The number of edges in k-quasi-planar graphs. SIAM J. on Discrete Mathematics 27(1), 550–561 (2013)

Grigoriev, A., Bodlaender, H.L.: Algorithms for graphs embeddable with few crossings per edge. Algorithmica 49(1), 1–11 (2007)

Hong, S.H., Eades, P., Katoh, N., Liotta, G., Schweitzer, P., Suzuki, Y.: A linear-time algorithm for testing outer-1-planarity. In: Wismath, S., Wolff, A. (eds.) GD 2013. LNCS, vol. 8242, pp. 71–82. 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)

Kaufmann, M., Ueckerdt, T.: The density of fan-planar graphs. CoRR abs/1403.6184 (2014), http://arxiv.org/abs/1403.6184

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

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

Schaefer, M.: The graph crossing number and its variants: A survey. Electronic J. of Combinatorics 20(2) (2013)

Suzuki, Y.: Re-embeddings of maximum 1-planar graphs. SIAM J. on Discrete Mathematics 24(4), 1527–1540 (2010)

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

Garey, M., Johnson, D.: Crossing Number is NP-Complete. SIAM Journal on Algebraic Discrete Methods 4(3), 312–316 (1983), doi:10.1137/0604033