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:10.3390/A13080194

Graph planarity by replacing cliques with paths

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

Research output: Contribution to journal › Article › peer-review

7 Scopus citations

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.

Original language	English (US)
Article number	194
Journal	Algorithms
Volume	13
Issue number	8
DOIs	https://doi.org/10.3390/A13080194
State	Published - Aug 2020
Externally published	Yes

Keywords

Cliques
K-planarity
NP-hardness
Paths
Planar graphs
Polynomial time reduction

ASJC Scopus subject areas

Theoretical Computer Science
Numerical Analysis
Computational Theory and Mathematics
Computational Mathematics

Access to Document

10.3390/A13080194

Cite this

@article{537b5ee63a6641f39ab4fb478809d10d,

title = "Graph planarity by replacing cliques with paths",

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

keywords = "Cliques, K-planarity, NP-hardness, Paths, Planar graphs, Polynomial time reduction",

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} 2020 by the authors.",

year = "2020",

month = aug,

doi = "10.3390/A13080194",

language = "English (US)",

volume = "13",

journal = "Algorithms",

issn = "1999-4893",

publisher = "Multidisciplinary Digital Publishing Institute (MDPI)",

number = "8",

}

TY - JOUR

T1 - Graph planarity by replacing cliques with paths

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 - 2020/8

Y1 - 2020/8

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

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

KW - Cliques

KW - K-planarity

KW - NP-hardness

KW - Paths

KW - Planar graphs

KW - Polynomial time reduction

UR - http://www.scopus.com/inward/record.url?scp=85090053981&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85090053981&partnerID=8YFLogxK

U2 - 10.3390/A13080194

DO - 10.3390/A13080194

M3 - Article

AN - SCOPUS:85090053981

SN - 1999-4893

VL - 13

JO - Algorithms

JF - Algorithms

IS - 8

M1 - 194

ER -

Graph planarity by replacing cliques with paths

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this