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 , 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
Depositing User: Administration GDEA
Date Deposited: 22 May 2015 09:03
Last Modified: 22 May 2015 09:03
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1433

Actions (login required)

View Item View Item