Turning Cliques into Paths to Achieve Planarity

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

Turning Cliques into Paths to Achieve Planarity

Dateien

Zu diesem Dokument gibt es keine Dateien.

Datum

2018

Autor:innen

Angelini, Patrizio

Eades, Peter

Hong, Seok-Hee

Klein, Karsten

Kobourov, Stephen

Liotta, Giuseppe

Navarra, Alfredo

Tappini, Alessandra

DOI (zitierfähiger Link)

https://doi.org/10.1007/978-3-030-04414-5_5

Sammlungen

Informatik und Informationswissenschaft

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

Fachgebiet (DDC)

004 Informatik

Konferenz

26th International Symposium, GD 2018, 26. Sept. 2018 - 28. Sept. 2018, Barcelona, Spain

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_5

BibTex

@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>

Universitätsbibliographie

Ja