@article{
	11391_1395960,
	author = {Bekos, Michael A and Cornelsen, Sabine and Grilli, Luca and Hong, Seok-Hee and Kaufmann, Michael},
	title = {On the Recognition of Fan-Planar and Maximal Outer-Fan-Planar Graphs},
	year = {2017},
	journal = {ALGORITHMICA},
	volume = {79},
	abstract = {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.},
	keywords = {Beyond planarity; Fan-planar graphs; Graph drawing;},
	url = {https://link.springer.com/content/pdf/10.1007%2Fs00453-016-0200-5.pdf},
	doi = {10.1007/s00453-016-0200-5},	
	pages = {401--427}
}

{"_id":"e5EykFijiMKFfgBiq","bibbaseid":"bekos-cornelsen-grilli-hong-kaufmann-ontherecognitionoffanplanarandmaximalouterfanplanargraphs-2017","downloads":0,"creationDate":"2018-11-29T17:08:09.073Z","title":"On the Recognition of Fan-Planar and Maximal Outer-Fan-Planar Graphs","author_short":["Bekos, M. A","Cornelsen, S.","Grilli, L.","Hong, S.","Kaufmann, M."],"year":2017,"bibtype":"article","biburl":"http://www.dmi.unipg.it/cybersecuritylab/temp_files/global.bib","bibdata":{"bibtype":"article","type":"article","author":[{"propositions":[],"lastnames":["Bekos"],"firstnames":["Michael","A"],"suffixes":[]},{"propositions":[],"lastnames":["Cornelsen"],"firstnames":["Sabine"],"suffixes":[]},{"propositions":[],"lastnames":["Grilli"],"firstnames":["Luca"],"suffixes":[]},{"propositions":[],"lastnames":["Hong"],"firstnames":["Seok-Hee"],"suffixes":[]},{"propositions":[],"lastnames":["Kaufmann"],"firstnames":["Michael"],"suffixes":[]}],"title":"On the Recognition of Fan-Planar and Maximal Outer-Fan-Planar Graphs","year":"2017","journal":"ALGORITHMICA","volume":"79","abstract":"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.","keywords":"Beyond planarity; Fan-planar graphs; Graph drawing;","url":"https://link.springer.com/content/pdf/10.1007%2Fs00453-016-0200-5.pdf","doi":"10.1007/s00453-016-0200-5","pages":"401–427","bibtex":"@article{\n\t11391_1395960,\n\tauthor = {Bekos, Michael A and Cornelsen, Sabine and Grilli, Luca and Hong, Seok-Hee and Kaufmann, Michael},\n\ttitle = {On the Recognition of Fan-Planar and Maximal Outer-Fan-Planar Graphs},\n\tyear = {2017},\n\tjournal = {ALGORITHMICA},\n\tvolume = {79},\n\tabstract = {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.},\n\tkeywords = {Beyond planarity; Fan-planar graphs; Graph drawing;},\n\turl = {https://link.springer.com/content/pdf/10.1007%2Fs00453-016-0200-5.pdf},\n\tdoi = {10.1007/s00453-016-0200-5},\t\n\tpages = {401--427}\n}\n","author_short":["Bekos, M. A","Cornelsen, S.","Grilli, L.","Hong, S.","Kaufmann, M."],"key":"11391_1395960","id":"11391_1395960","bibbaseid":"bekos-cornelsen-grilli-hong-kaufmann-ontherecognitionoffanplanarandmaximalouterfanplanargraphs-2017","role":"author","urls":{"Paper":"https://link.springer.com/content/pdf/10.1007%2Fs00453-016-0200-5.pdf"},"keyword":["Beyond planarity; Fan-planar graphs; Graph drawing;"],"metadata":{"authorlinks":{}},"html":""},"search_terms":["recognition","fan","planar","maximal","outer","fan","planar","graphs","bekos","cornelsen","grilli","hong","kaufmann"],"keywords":["beyond planarity; fan-planar graphs; graph drawing;"],"authorIDs":[],"dataSources":["3MX69j2byatx2gxQG"]}