Publikation: Turning Cliques into Paths to Achieve Planarity
Lade...
Dateien
Zu diesem Dokument gibt es keine Dateien.
Datum
2018
Autor:innen
Angelini, Patrizio
Eades, Peter
Hong, Seok-Hee
Kobourov, Stephen
Liotta, Giuseppe
Navarra, Alfredo
Tappini, Alessandra
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
Beitrag zu einem Konferenzband
Publikationsstatus
Published
Erschienen in
BIEDL, Therese, ed., Andreas KERREN, ed.. Graph Drawing and Network Visualization : 26th International Symposium, GD 2018, Barcelona, Spain, September 26-28, 2018, proceedings. Cham: Springer, 2018, pp. 67-74. Lecture Notes in Computer Science. 11282. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-030-04413-8. Available under: doi: 10.1007/978-3-030-04414-5_5
Zusammenfassung
Motivated by hybrid graph representations, we introduce and study the following beyond-planarity problem, which we call h -Clique2Path Planarity: Given a graph G, whose vertices are partitioned into subsets of size at most h, each inducing a clique, remove edges from each clique so that the subgraph induced by each subset is a path, in such a way that the resulting subgraph of G is planar. We study this problem when G is a simple topological graph, and establish its complexity in relation to k-planarity. 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, for any h, when G is 1-plane
Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
004 Informatik
Schlagwörter
Konferenz
26th International Symposium, GD 2018, 26. Sept. 2018 - 28. Sept. 2018, Barcelona, Spain
Rezension
undefined / . - undefined, undefined
Zitieren
ISO 690
ANGELINI, Patrizio, Peter EADES, Seok-Hee HONG, Karsten KLEIN, Stephen KOBOUROV, Giuseppe LIOTTA, Alfredo NAVARRA, Alessandra TAPPINI, 2018. Turning Cliques into Paths to Achieve Planarity. 26th International Symposium, GD 2018. Barcelona, Spain, 26. Sept. 2018 - 28. Sept. 2018. In: BIEDL, Therese, ed., Andreas KERREN, ed.. Graph Drawing and Network Visualization : 26th International Symposium, GD 2018, Barcelona, Spain, September 26-28, 2018, proceedings. Cham: Springer, 2018, pp. 67-74. Lecture Notes in Computer Science. 11282. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-030-04413-8. Available under: doi: 10.1007/978-3-030-04414-5_5BibTex
@inproceedings{Angelini2018-12-18Turni-44694,
year={2018},
doi={10.1007/978-3-030-04414-5_5},
title={Turning Cliques into Paths to Achieve Planarity},
number={11282},
isbn={978-3-030-04413-8},
issn={0302-9743},
publisher={Springer},
address={Cham},
series={Lecture Notes in Computer Science},
booktitle={Graph Drawing and Network Visualization : 26th International Symposium, GD 2018, Barcelona, Spain, September 26-28, 2018, proceedings},
pages={67--74},
editor={Biedl, Therese and Kerren, Andreas},
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}
}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/44694">
<dcterms:title>Turning Cliques into Paths to Achieve Planarity</dcterms:title>
<dc:contributor>Hong, Seok-Hee</dc:contributor>
<foaf:homepage rdf:resource="http://localhost:8080/"/>
<bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/44694"/>
<dc:creator>Eades, Peter</dc:creator>
<dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
<dc:creator>Liotta, Giuseppe</dc:creator>
<dc:contributor>Navarra, Alfredo</dc:contributor>
<dc:contributor>Kobourov, Stephen</dc:contributor>
<dcterms:issued>2018-12-18</dcterms:issued>
<dc:creator>Angelini, Patrizio</dc:creator>
<dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-01-23T13:37:44Z</dc:date>
<dc:creator>Kobourov, Stephen</dc:creator>
<dc:creator>Tappini, Alessandra</dc:creator>
<void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
<dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-01-23T13:37:44Z</dcterms:available>
<dc:language>eng</dc:language>
<dc:contributor>Klein, Karsten</dc:contributor>
<dc:contributor>Liotta, Giuseppe</dc:contributor>
<dc:creator>Navarra, Alfredo</dc:creator>
<dcterms:abstract xml:lang="eng">Motivated by hybrid graph representations, we introduce and study the following beyond-planarity problem, which we call h -Clique2Path Planarity: Given a graph G, whose vertices are partitioned into subsets of size at most h, each inducing a clique, remove edges from each clique so that the subgraph induced by each subset is a path, in such a way that the resulting subgraph of G is planar. We study this problem when G is a simple topological graph, and establish its complexity in relation to k-planarity. 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, for any h, when G is 1-plane</dcterms:abstract>
<dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
<dc:contributor>Angelini, Patrizio</dc:contributor>
<dc:creator>Hong, Seok-Hee</dc:creator>
<dc:contributor>Tappini, Alessandra</dc:contributor>
<dc:creator>Klein, Karsten</dc:creator>
<dc:contributor>Eades, Peter</dc:contributor>
</rdf:Description>
</rdf:RDF>Interner Vermerk
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Prüfungsdatum der Dissertation
Finanzierungsart
Kommentar zur Publikation
Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Ja
