Algorithms (Aug 2020)

Graph Planarity by Replacing Cliques with Paths

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

DOI
https://doi.org/10.3390/a13080194
Journal volume & issue
Vol. 13, no. 8
p. 194

Abstract

Read online

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.

Keywords