Publikation:

Graph Planarity by Replacing Cliques with Paths

Lade...
Vorschaubild

Dateien

Angelini_2-1p8cgc06b5k3p4.pdf
Angelini_2-1p8cgc06b5k3p4.pdfGröße: 434.17 KBDownloads: 217

Datum

2020

Autor:innen

Angelini, Patrizio
Eades, Peter
Hong, Seok-Hee
Kobourov, Stephen
Liotta, Giuseppe
Navarra, Alfredo
Tappini, Alessandra

Herausgeber:innen

Kontakt

ISSN der Zeitschrift

Electronic ISSN

ISBN

Bibliografische Daten

Verlag

Schriftenreihe

Auflagebezeichnung

DOI (zitierfähiger Link)
ArXiv-ID

Internationale Patentnummer

Link zur Lizenz

Angaben zur Forschungsförderung

Projekt

Open Access-Veröffentlichung
Open Access Gold
Core Facility der Universität Konstanz

Gesperrt bis

Titel in einer weiteren Sprache

Publikationstyp
Zeitschriftenartikel
Publikationsstatus
Published

Erschienen in

Algorithms. MDPI. 2020, 13(8), 194. eISSN 1999-4893. Available under: doi: 10.3390/a13080194

Zusammenfassung

This paper introduces and studies the following beyond-planarity problem, which we call h-Clique2Path Planarity. Let G be a simple topological graph whose vertices are partitioned into subsets of size at most h, each inducing a clique. h-Clique2Path Planarity asks whether it is possible to obtain a planar subgraph of G by removing edges from each clique so that the subgraph induced by each subset is a path. We investigate the complexity of this problem in relation to k-planarity. In particular, we prove that h-Clique2Path Planarity is NP-complete even when h=4 and G is a simple 3-plane graph, while it can be solved in linear time when G is a simple 1-plane graph, for any value of h. Our results contribute to the growing fields of hybrid planarity and of graph drawing beyond planarity.

Zusammenfassung in einer weiteren Sprache

Fachgebiet (DDC)
004 Informatik

Schlagwörter

planar graphs; k-planarity; NP-hardness; polynomial time reduction; cliques; paths

Konferenz

Rezension
undefined / . - undefined, undefined

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Zugehörige Datensätze in KOPS

Zitieren

ISO 690ANGELINI, Patrizio, Peter EADES, Seok-Hee HONG, Karsten KLEIN, Stephen KOBOUROV, Giuseppe LIOTTA, Alfredo NAVARRA, Alessandra TAPPINI, 2020. Graph Planarity by Replacing Cliques with Paths. In: Algorithms. MDPI. 2020, 13(8), 194. eISSN 1999-4893. Available under: doi: 10.3390/a13080194
BibTex
@article{Angelini2020-08-13Graph-51244,
  year={2020},
  doi={10.3390/a13080194},
  title={Graph Planarity by Replacing Cliques with Paths},
  number={8},
  volume={13},
  journal={Algorithms},
  author={Angelini, Patrizio and Eades, Peter and Hong, Seok-Hee and Klein, Karsten and Kobourov, Stephen and Liotta, Giuseppe and Navarra, Alfredo and Tappini, Alessandra},
  note={Article Number: 194}
}
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/51244">
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/51244/1/Angelini_2-1p8cgc06b5k3p4.pdf"/>
    <dc:contributor>Eades, Peter</dc:contributor>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dcterms:title>Graph Planarity by Replacing Cliques with Paths</dcterms:title>
    <dc:language>eng</dc:language>
    <dc:contributor>Angelini, Patrizio</dc:contributor>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2020-10-07T09:35:26Z</dcterms:available>
    <dc:creator>Angelini, Patrizio</dc:creator>
    <dc:rights>Attribution 4.0 International</dc:rights>
    <dcterms:rights rdf:resource="http://creativecommons.org/licenses/by/4.0/"/>
    <dc:contributor>Kobourov, Stephen</dc:contributor>
    <dc:creator>Liotta, Giuseppe</dc:creator>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/51244"/>
    <dc:creator>Tappini, Alessandra</dc:creator>
    <dc:creator>Kobourov, Stephen</dc:creator>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2020-10-07T09:35:26Z</dc:date>
    <dcterms:abstract xml:lang="eng">This paper introduces and studies the following beyond-planarity problem, which we call h-Clique2Path Planarity. Let G be a simple topological graph whose vertices are partitioned into subsets of size at most h, each inducing a clique. h-Clique2Path Planarity asks whether it is possible to obtain a planar subgraph of G by removing edges from each clique so that the subgraph induced by each subset is a path. We investigate the complexity of this problem in relation to k-planarity. In particular, we prove that h-Clique2Path Planarity is NP-complete even when h=4 and G is a simple 3-plane graph, while it can be solved in linear time when G is a simple 1-plane graph, for any value of h. Our results contribute to the growing fields of hybrid planarity and of graph drawing beyond planarity.</dcterms:abstract>
    <dc:contributor>Tappini, Alessandra</dc:contributor>
    <dc:contributor>Navarra, Alfredo</dc:contributor>
    <dc:contributor>Hong, Seok-Hee</dc:contributor>
    <dcterms:issued>2020-08-13</dcterms:issued>
    <dc:creator>Eades, Peter</dc:creator>
    <dc:creator>Klein, Karsten</dc:creator>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:contributor>Liotta, Giuseppe</dc:contributor>
    <dc:creator>Navarra, Alfredo</dc:creator>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:creator>Hong, Seok-Hee</dc:creator>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/51244/1/Angelini_2-1p8cgc06b5k3p4.pdf"/>
    <dc:contributor>Klein, Karsten</dc:contributor>
  </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
Ja
Diese Publikation teilen