Turning cliques into paths to achieve planarity

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

doi:10.1007/978-3-030-04414-5_5

Turning cliques into paths to achieve planarity

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

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

8 Scopus citations

Abstract

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.

Original language	English (US)
Title of host publication	Graph Drawing and Network Visualization - 26th International Symposium, GD 2018, Proceedings
Editors	Therese Biedl, Andreas Kerren
Publisher	Springer-Verlag
Pages	67-74
Number of pages	8
ISBN (Print)	9783030044138
DOIs	https://doi.org/10.1007/978-3-030-04414-5_5
State	Published - 2018
Event	26th International Symposium on Graph Drawing and Network Visualization, GD 2018 - Barcelona, Spain Duration: Sep 26 2018 → Sep 28 2018

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	11282 LNCS

Other

Other	26th International Symposium on Graph Drawing and Network Visualization, GD 2018
Country/Territory	Spain
City	Barcelona
Period	9/26/18 → 9/28/18

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-030-04414-5_5

Cite this

Angelini, P., Eades, P., Hong, S. H., Klein, K., Kobourov, S., Liotta, G., Navarra, A., & Tappini, A. (2018). Turning cliques into paths to achieve planarity. In T. Biedl, & A. Kerren (Eds.), Graph Drawing and Network Visualization - 26th International Symposium, GD 2018, Proceedings (pp. 67-74). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11282 LNCS). Springer-Verlag. https://doi.org/10.1007/978-3-030-04414-5_5

Turning cliques into paths to achieve planarity. / Angelini, Patrizio; Eades, Peter; Hong, Seok Hee et al.
Graph Drawing and Network Visualization - 26th International Symposium, GD 2018, Proceedings. ed. / Therese Biedl; Andreas Kerren. Springer-Verlag, 2018. p. 67-74 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11282 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Angelini, P, Eades, P, Hong, SH, Klein, K, Kobourov, S, Liotta, G, Navarra, A & Tappini, A 2018, Turning cliques into paths to achieve planarity. in T Biedl & A Kerren (eds), Graph Drawing and Network Visualization - 26th International Symposium, GD 2018, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11282 LNCS, Springer-Verlag, pp. 67-74, 26th International Symposium on Graph Drawing and Network Visualization, GD 2018, Barcelona, Spain, 9/26/18. https://doi.org/10.1007/978-3-030-04414-5_5

Angelini P, Eades P, Hong SH, Klein K, Kobourov S, Liotta G et al. Turning cliques into paths to achieve planarity. In Biedl T, Kerren A, editors, Graph Drawing and Network Visualization - 26th International Symposium, GD 2018, Proceedings. Springer-Verlag. 2018. p. 67-74. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-04414-5_5

Angelini, Patrizio ; Eades, Peter ; Hong, Seok Hee et al. / Turning cliques into paths to achieve planarity. Graph Drawing and Network Visualization - 26th International Symposium, GD 2018, Proceedings. editor / Therese Biedl ; Andreas Kerren. Springer-Verlag, 2018. pp. 67-74 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{1c490da84767491690f246ce3e2c175e,

title = "Turning cliques into paths to achieve planarity",

abstract = "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.",

author = "Patrizio Angelini and Peter Eades and Hong, \{Seok Hee\} and Karsten Klein and Stephen Kobourov and Giuseppe Liotta and Alfredo Navarra and Alessandra Tappini",

note = "Publisher Copyright: {\textcopyright} Springer Nature Switzerland AG 2018.; 26th International Symposium on Graph Drawing and Network Visualization, GD 2018 ; Conference date: 26-09-2018 Through 28-09-2018",

year = "2018",

doi = "10.1007/978-3-030-04414-5\_5",

language = "English (US)",

isbn = "9783030044138",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer-Verlag",

pages = "67--74",

editor = "Therese Biedl and Andreas Kerren",

booktitle = "Graph Drawing and Network Visualization - 26th International Symposium, GD 2018, Proceedings",

}

TY - GEN

T1 - Turning cliques into paths to achieve planarity

AU - Angelini, Patrizio

AU - Eades, Peter

AU - Hong, Seok Hee

AU - Klein, Karsten

AU - Kobourov, Stephen

AU - Liotta, Giuseppe

AU - Navarra, Alfredo

AU - Tappini, Alessandra

PY - 2018

Y1 - 2018

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/85059092003

UR - https://www.scopus.com/pages/publications/85059092003#tab=citedBy

U2 - 10.1007/978-3-030-04414-5_5

DO - 10.1007/978-3-030-04414-5_5

M3 - Conference contribution

SN - 9783030044138

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 67

EP - 74

BT - Graph Drawing and Network Visualization - 26th International Symposium, GD 2018, Proceedings

A2 - Biedl, Therese

A2 - Kerren, Andreas

PB - Springer-Verlag

T2 - 26th International Symposium on Graph Drawing and Network Visualization, GD 2018

Y2 - 26 September 2018 through 28 September 2018

ER -

Turning cliques into paths to achieve planarity

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this