Publikation:

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

Vorschaubild

Dateien

Zu diesem Dokument gibt es keine Dateien.

Datum

2014

Autor:innen

Bekos, Michael A.
Grilli, Luca
Hong, Seok-Hee
Kaufmann, Michael

Herausgeber:innen

Kontakt

ISSN der Zeitschrift

Electronic ISSN

ISBN

Bibliografische Daten

Verlag

Schriftenreihe

Auflagebezeichnung

URI (zitierfähiger Link)
DOI (zitierfähiger Link)
https://doi.org/10.1007/978-3-662-45803-7_17
ArXiv-ID

Internationale Patentnummer

Angaben zur Forschungsförderung

Projekt

Open Access-Veröffentlichung

Sammlungen

Informatik und Informationswissenschaft: Publikationen
Core Facility der Universität Konstanz

Gesperrt bis

Titel in einer weiteren Sprache

Publikationstyp
Beitrag zu einem Konferenzband
Publikationsstatus
Published

Erschienen 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, 2014, pp. 198-209. Lecture Notes in Computer Science. 8871. ISBN 978-3-662-45802-0. Available under: doi: 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.

Zusammenfassung in einer weiteren Sprache

Fachgebiet (DDC)
004 Informatik

Schlagwörter

Konferenz

22nd International Symposium, Graph Drawing 2014, 24. Sept. 2014 - 26. Sept. 2014, Würzburg
Rezension
undefined / . - undefined, undefined

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Zugehörige Datensätze in KOPS

Zitieren

ISO 690BEKOS, 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. Sept. 2014 - 26. Sept. 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, 2014, pp. 198-209. Lecture Notes in Computer Science. 8871. ISBN 978-3-662-45802-0. Available under: doi: 10.1007/978-3-662-45803-7_17
BibTex
@inproceedings{Bekos2014recog-30511,
  year={2014},
  doi={10.1007/978-3-662-45803-7_17},
  title={On the recognition of fan-planar and maximal outer-fan-planar graphs},
  number={8871},
  isbn={978-3-662-45802-0},
  publisher={Springer},
  address={Berlin [u.a.]},
  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}
}
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/30511">
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2015-03-24T09:42:51Z</dc:date>
    <dcterms:title>On the recognition of fan-planar and maximal outer-fan-planar graphs</dcterms:title>
    <dc:contributor>Cornelsen, Sabine</dc:contributor>
    <dc:creator>Hong, Seok-Hee</dc:creator>
    <dc:contributor>Bekos, Michael A.</dc:contributor>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2015-03-24T09:42:51Z</dcterms:available>
    <dc:contributor>Grilli, Luca</dc:contributor>
    <dc:contributor>Kaufmann, Michael</dc:contributor>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <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.&lt;br /&gt;&lt;br /&gt;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.</dcterms:abstract>
    <dc:contributor>Hong, Seok-Hee</dc:contributor>
    <dc:creator>Grilli, Luca</dc:creator>
    <dc:creator>Kaufmann, Michael</dc:creator>
    <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/30511"/>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:creator>Cornelsen, Sabine</dc:creator>
    <dc:language>eng</dc:language>
    <dc:creator>Bekos, Michael A.</dc:creator>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dcterms:issued>2014</dcterms:issued>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
  </rdf:Description>
</rdf:RDF>

Interner Vermerk

xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter

Kontakt
URL der Originalveröffentl.

Prüfdatum der URL

Prüfungsdatum der Dissertation

Finanzierungsart

Kommentar zur Publikation

Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Ja
Begutachtet
Diese Publikation teilen