On the recognition of fan-planar and maximal outer-fan-planar graphs

Cite This

Files in this item

Files Size Format View

There are no files associated with this item.

BEKOS, Michael A., Sabine CORNELSEN, Luca GRILLI, Seok-Hee HONG, Michael KAUFMANN, 2014. On the recognition of fan-planar and maximal outer-fan-planar graphs. 22nd International Symposium, Graph Drawing 2014. Würzburg, Sep 24, 2014 - Sep 26, 2014. In: CHRISTIAN DUNCAN ..., , ed.. Graph Drawing : 22nd International Symposium, GD 2014, Würzburg, Germany, September 24-26, 2014 ; revised selected papers. Berlin [u.a.]:Springer, pp. 198-209. ISBN 978-3-662-45802-0. Available under: doi: 10.1007/978-3-662-45803-7_17

@inproceedings{Bekos2014recog-30511, title={On the recognition of fan-planar and maximal outer-fan-planar graphs}, year={2014}, doi={10.1007/978-3-662-45803-7_17}, number={8871}, isbn={978-3-662-45802-0}, address={Berlin [u.a.]}, publisher={Springer}, series={Lecture Notes in Computer Science}, booktitle={Graph Drawing : 22nd International Symposium, GD 2014, Würzburg, Germany, September 24-26, 2014 ; revised selected papers}, pages={198--209}, editor={Christian Duncan ...}, author={Bekos, Michael A. and Cornelsen, Sabine and Grilli, Luca and Hong, Seok-Hee and Kaufmann, Michael} }

On the recognition of fan-planar and maximal outer-fan-planar graphs Cornelsen, Sabine Bekos, Michael A. Grilli, Luca Cornelsen, Sabine Hong, Seok-Hee 2015-03-24T09:42:51Z 2014 eng Hong, Seok-Hee Bekos, Michael A. 2015-03-24T09:42:51Z 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.<br /><br />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. Kaufmann, Michael Kaufmann, Michael Grilli, Luca

This item appears in the following Collection(s)

Search KOPS


Browse

My Account