Publikation: Graph Planarity by Replacing Cliques with Paths
Dateien
Datum
Autor:innen
Herausgeber:innen
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
URI (zitierfähiger Link)
DOI (zitierfähiger Link)
Internationale Patentnummer
Link zur Lizenz
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
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)
Schlagwörter
Konferenz
Rezension
Zitieren
ISO 690
ANGELINI, 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/a13080194BibTex
@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>