On the recognition of fan-planar and maximal outer-fan-planar graphs
| Type of Publication: | Contribution to a conference collection |
| Author: | Bekos, Michael A.; Cornelsen, Sabine; Grilli, Luca; Hong, Seok-Hee; Kaufmann, Michael |
| Year of publication: | 2014 |
| Conference: | 22nd International Symposium, Graph Drawing 2014, Sep 24, 2014 - Sep 26, 2014, Würzburg |
| Published in: | Graph Drawing : 22nd International Symposium, GD 2014, Würzburg, Germany, September 24-26, 2014 ; revised selected papers / Christian Duncan ... (ed.). - Berlin [u.a.] : Springer, 2014. - (Lecture Notes in Computer Science ; 8871). - pp. 198-209. - ISBN 978-3-662-45802-0 |
| DOI (citable link): | https://dx.doi.org/10.1007/978-3-662-45803-7_17 |
| Summary: |
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. |
| Subject (DDC): | 004 Computer Science |
| Bibliography of Konstanz: | Yes |
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} }
This item appears in the following Collection(s)
Search KOPS
Browse
My Account
