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
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

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{dbeaa4f5fa714e79a2e3146f511bc4db,

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/inward/citedby.url?scp=85059092003&partnerID=8YFLogxK

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

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

M3 - Conference contribution

AN - SCOPUS:85059092003

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