M. A. Bekos, S. Cornelsen, L. Grilli, S. Hong and M. Kaufmann, "On the Recognition of FanPlanar and Maximal OuterFanPlanar Graphs", Proceedings of Graph Drawing 2014, pp. 198209, LNCS, Springer, 2014.
Fanplanar graphs were recently introduced as a generalization of 1planar graphs. A graph
is fanplanar 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 outerfanplanar if
it has a fanplanar embedding in which every vertex is on the outer face. If, in addition, the insertion
of an edge destroys its outerfanplanarity, then it is maximal outerfanplanar.
In this paper, we present a polynomialtime algorithm to test whether a given graph is maximal outer
fanplanar. The algorithm can also be employed to produce an outerfanplanar embedding, if one
exists. On the negative side, we show that testing fanplanarity of a graph is NPhard, for the case
where the rotation system (i.e., the cyclic order of the edges around each vertex) is given.
