On the Recognition of Fan-Planar and Maximal Outer-Fan-Planar Graphs

No Thumbnail Available
Files
There are no files associated with this item.
Date
2017
Authors
Bekos, Michael A.
Grilli, Luca
Hong, Seok-Hee
Kaufmann, Michael
Editors
Contact
Journal ISSN
Electronic ISSN
ISBN
Bibliographical data
Publisher
Series
URI (citable link)
DOI (citable link)
ArXiv-ID
International patent number
Link to the license
oops
EU project number
Project
Open Access publication
Restricted until
Title in another language
Research Projects
Organizational Units
Journal Issue
Publication type
Journal article
Publication status
Published
Published in
Algorithmica ; 79 (2017), 2. - pp. 401-427. - ISSN 0178-4617. - eISSN 1432-0541
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.
Summary in another language
Subject (DDC)
004 Computer Science
Keywords
Fan-planar graphs, Beyond planarity, Graph drawing
Conference
Review
undefined / . - undefined, undefined. - (undefined; undefined)
Cite This
ISO 690BEKOS, Michael A., Sabine CORNELSEN, Luca GRILLI, Seok-Hee HONG, Michael KAUFMANN, 2017. On the Recognition of Fan-Planar and Maximal Outer-Fan-Planar Graphs. In: Algorithmica. 79(2), pp. 401-427. ISSN 0178-4617. eISSN 1432-0541. Available under: doi: 10.1007/s00453-016-0200-5
BibTex
@article{Bekos2017-10Recog-40478,
  year={2017},
  doi={10.1007/s00453-016-0200-5},
  title={On the Recognition of Fan-Planar and Maximal Outer-Fan-Planar Graphs},
  number={2},
  volume={79},
  issn={0178-4617},
  journal={Algorithmica},
  pages={401--427},
  author={Bekos, Michael A. and Cornelsen, Sabine and Grilli, Luca and Hong, Seok-Hee and Kaufmann, Michael}
}
RDF
<rdf:RDF
    xmlns:dcterms="http://purl.org/dc/terms/"
    xmlns:dc="http://purl.org/dc/elements/1.1/"
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
    xmlns:bibo="http://purl.org/ontology/bibo/"
    xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
    xmlns:foaf="http://xmlns.com/foaf/0.1/"
    xmlns:void="http://rdfs.org/ns/void#"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > 
  <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/40478">
    <dc:contributor>Kaufmann, Michael</dc:contributor>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2017-11-03T10:26:14Z</dcterms:available>
    <dc:contributor>Grilli, Luca</dc:contributor>
    <dcterms:abstract xml:lang="eng">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.</dcterms:abstract>
    <dc:creator>Kaufmann, Michael</dc:creator>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2017-11-03T10:26:14Z</dc:date>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dcterms:title>On the Recognition of Fan-Planar and Maximal Outer-Fan-Planar Graphs</dcterms:title>
    <dc:contributor>Bekos, Michael A.</dc:contributor>
    <dc:creator>Grilli, Luca</dc:creator>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:contributor>Cornelsen, Sabine</dc:contributor>
    <dc:creator>Cornelsen, Sabine</dc:creator>
    <dc:language>eng</dc:language>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/40478"/>
    <dc:creator>Bekos, Michael A.</dc:creator>
    <dcterms:issued>2017-10</dcterms:issued>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dc:creator>Hong, Seok-Hee</dc:creator>
    <dc:contributor>Hong, Seok-Hee</dc:contributor>
  </rdf:Description>
</rdf:RDF>
Internal note
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Contact
URL of original publication
Test date of URL
Examination date of dissertation
Method of financing
Comment on publication
Alliance license
Corresponding Authors der Uni Konstanz vorhanden
International Co-Authors
Bibliography of Konstanz
Yes
Refereed