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

Publikationstyp: Beitrag zu einer Konferenz
Autor/innen: Bekos, Michael A.; Cornelsen, Sabine; Grilli, Luca; Hong, Seok-Hee; Kaufmann, Michael
Erscheinungsjahr: 2014
Konferenz: 22nd International Symposium, Graph Drawing 2014, 24. Sep 2014 - 26. Sep 2014, Würzburg
Erschienen in: Graph Drawing : 22nd International Symposium, GD 2014, Würzburg, Germany, September 24-26, 2014 ; revised selected papers / Christian Duncan ... (Hrsg.). - Berlin [u.a.] : Springer, 2014. - (Lecture Notes in Computer Science ; 8871). - S. 198-209. - ISBN 978-3-662-45802-0
DOI (zitierfähiger Link): https://dx.doi.org/10.1007/978-3-662-45803-7_17
Zusammenfassung:
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.
Fachgebiet (DDC): 004 Informatik
Universitätsbibliographie: Ja

Zitieren

Dateien zu dieser Ressource

Dateien Größe Format Anzeige

Zu diesem Dokument gibt es keine Dateien.

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, 24. Sep 2014 - 26. Sep 2014. In: CHRISTIAN DUNCAN ..., , ed.. Graph Drawing : 22nd International Symposium, GD 2014, Würzburg, Germany, September 24-26, 2014 ; revised selected papers. 22nd International Symposium, Graph Drawing 2014. Würzburg, 24. Sep 2014 - 26. Sep 2014. Berlin [u.a.]:Springer, pp. 198-209. ISBN 978-3-662-45802-0

@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

Das Dokument erscheint in:

KOPS Suche


Stöbern

Mein Benutzerkonto