Loading...
Graph Planarity by Replacing Cliques with Paths
Angelini, Patrizio
Eades, Peter Hong, Seok-Hee Klein, Karsten Kobourov, Stephan Liotta, Giuseppe Navarra, Alfredo Tappini, Alessandra
Eades, Peter
Hong, Seok-Hee
Klein, Karsten
Kobourov, Stephan
Liotta, Giuseppe
Navarra, Alfredo
Tappini, Alessandra
Citations
Altmetric:
Abstract
This paper introduces and studies the following beyond-planarity problem, which we call h-Clique2Path Planarity. Let G be a simple topological graph whose vertices are partitioned into subsets of size at most h, each inducing a clique. h-Clique2Path Planarity asks whether it is possible to obtain a planar subgraph of G by removing edges from each clique so that the subgraph induced by each subset is a path. We investigate the complexity of this problem in relation to k-planarity. In particular, 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 when G is a simple 1-plane graph, for any value of h. Our results contribute to the growing fields of hybrid planarity and of graph drawing beyond planarity.
Description
Date
2020
Journal Title
Journal ISSN
Volume Title
Publisher
Research Projects
Organizational Units
Journal Issue
Keywords
Planar graphs, K-planarity, NP-hardness, Polynomial time reduction, Cliques, Paths
Citation
Angelini, Patrizio, Peter Eades, Seok-Hee Hong, et al. “Graph Planarity by Replacing Cliques with Paths.” Algorithms 13 (8): 194. 2020.
ISBN
License
Attribution 4.0 International