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
N1 - Funding Information:
This work began at the Bertinoro Workshop on Graph Drawing 2018. Research was partially supported by DFG grant Ka812/17-1 and MIUR-DAAD Joint Mobility Program n.57397196 (PA), by Young Scholar Fund/AFF-Univ. Konstanz (KK), by NSF grants CCF-1740858-CCF-1712119 (SK), by project “Algoritmi e sistemi di analisi visuale di reti complesse e di grandi dimensioni”-Ric. di Base 2018, Dip. Ingegneria-Univ. Perugia (GL, AT), by project GEO-SAFE n.H2020-691161 (AN).
Funding Information:
This work began at the Bertinoro Workshop on Graph Drawing 2018. Research was partially supported by DFG grant Ka812/17-1 and MIUR-DAAD Joint Mobility Program n.57397196 (PA), by Young Scholar Fund/AFF - Univ. Konstanz (KK), by NSF grants CCF-1740858 - CCF-1712119 (SK), by project “Algoritmi e sistemi di analisi visuale di reti complesse e di grandi dimensioni” - Ric. di Base 2018, Dip. Ingegneria - Univ. Perugia (GL, AT), by project GEO-SAFE n.H2020-691161 (AN).
Publisher Copyright:
© Springer Nature Switzerland AG 2018.
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 - http://www.scopus.com/inward/record.url?scp=85059092003&partnerID=8YFLogxK
UR - http://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 -