Publikation: On the Recognition of Fan-Planar and Maximal Outer-Fan-Planar Graphs
Dateien
Datum
Autor:innen
Herausgeber:innen
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
DOI (zitierfähiger Link)
Internationale Patentnummer
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Core Facility der Universität Konstanz
Titel in einer weiteren Sprache
Publikationstyp
Publikationsstatus
Erschienen in
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 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.
Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
Schlagwörter
Konferenz
Rezension
Zitieren
ISO 690
BEKOS, 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. 2017, 79(2), pp. 401-427. ISSN 0178-4617. eISSN 1432-0541. Available under: doi: 10.1007/s00453-016-0200-5BibTex
@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>