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 linear‐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‐complete, for the case where the rotation system (i.e., the cyclic order of the edges around each vertex) is given.
