On the Recognition of FanPlanar and Maximal OuterFanPlanar GraphsBekos, Michael A. and Cornelsen, Sabine and Grilli, Luca and Hong, SeokHee and Kaufmann, Michael (2014) On the Recognition of FanPlanar and Maximal OuterFanPlanar Graphs. In: Graph Drawing 22nd International Symposium, GD 2014, September 2426, 2014 , pp. 198209(Official URL: http://dx.doi.org/10.1007/9783662458037_17). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783662458037_17
AbstractFanplanar 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 outerfanplanar. 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.
Actions (login required)
