On the Recognition of Fan-Planar and Maximal Outer-Fan-Planar Graphs

Bekos, Michael A. and Cornelsen, Sabine and Grilli, Luca and Hong, Seok-Hee and Kaufmann, Michael (2014) On the Recognition of Fan-Planar and Maximal Outer-Fan-Planar Graphs. In: Graph Drawing 22nd International Symposium, GD 2014, September 24-26, 2014, Würzburg, Germany , pp. 198-209 (Official URL: http://dx.doi.org/10.1007/978-3-662-45803-7_17).

Full text not available from this repository.


Fan-planar graphs were recently introduced as a generalization of 1-planar graphs. A graph is fan-planar if it can be embedded in the plane, such that each edge that is crossed more than once, is crossed by a bundle of two or more edges incident to a common vertex. A graph is outer-fan-planar if it has a fan-planar embedding in which every vertex is on the outer face. If, in addition, the insertion of an edge destroys its outer-fan-planarity, then it is maximal outer-fan-planar. In this paper, we present a polynomial-time algorithm to test whether a given graph is maximal outer-fan-planar. The algorithm can also be employed to produce an outer-fan-planar embedding, if one exists. On the negative side, we show that testing fan-planarity of a graph is NP-hard, for the case where the rotation system (i.e., the cyclic order of the edges around each vertex) is given.

Item Type:Conference Paper
Additional Information:10.1007/978-3-662-45803-7_17
Classifications:G Algorithms and Complexity > G.420 Crossings
M Methods > M.900 Tree
P Styles > P.540 Planar
P Styles > P.999 Others
Z Theory > Z.750 Topology
ID Code:1433

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)

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)

Argyriou, E.N., Bekos, M.A., Symvonis, A.: The straight-line RAC drawing problem is NP-hard. J. Graph Algorithms Appl. 16(2), 569–597 (2012)

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)

Bekos, M.A., Cornelsen, S., Grilli, L., Hong, S.H., Kaufmann, M.: On the recognition of fan-planar and maximal outer-fan-planar graphs. CoRR abs/1409.0461 (September 2014)

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)

Reisi Dehkordi, H., Nguyen, Q., Eades, P., Hong, S.-H.: Circular graph drawings with large crossing angles. In: Ghosh, S.K., Tokuyama, T. (eds.) WALCOM 2013. LNCS, vol. 7748, pp. 298–309. Springer, Heidelberg (2013)

Didimo, W., Eades, P., Liotta, G.: Drawing graphs with right angle crossings. Theor. Comput. Sci. 412(39), 5156–5166 (2011)

Eades, P., Hong, S.H., Katoh, N., Liotta, G., Schweitzer, P., Suzuki, Y.: A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system. Theor. Comput. Sci. 513, 65–76 (2013)

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

Eggleton, R.: Rectilinear drawings of graphs. Utilitas Mathematica 29, 149–172 (1986)

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

Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)

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

Gutwenger, C., Mutzel, P.: A linear time implementation of SPQR-trees. In: Marks, J. (ed.) GD 2000. LNCS, vol. 1984, pp. 77–90. Springer, Heidelberg (2001)

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., Nagamochi, H.: Testing full outer-2-planarity in linear time. Technical Report 2014-003, Department of Applied Mathematics and Physics, Kyoto University (2014)

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

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)

Pach, J., Radoičić, R., Tóth, G.: Relaxing planarity for topological graphs. In: Akiyama, J., Kano, M. (eds.) JCDCG 2002. LNCS, vol. 2866, pp. 221–232. Springer, Heidelberg (2003)

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

Purchase, H.C.: Effective information visualisation: a study of graph drawing aesthetics and algorithms. Interacting with Computers 13(2), 147–162 (2000)

Ringel, G.: Ein Sechsfarbenproblem auf der Kugel. Abh. Math. Sem. Univ. Hamburg 29, 107–117 (1965)