Inicio  /  Algorithms  /  Vol: 13 Par: 8 (2020)  /  Artículo
ARTÍCULO
TITULO

Graph Planarity by Replacing Cliques with Paths

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

Resumen

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" role="presentation">h=4h=4 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.

 Artículos similares

       
 
Greg White    
Airport pavements have always evolved to keep pace with the demands of new aircraft. As aircraft weights and tyre pressures increase, stronger, new pavements are designed and existing pavements are rehabilitated or upgraded. The narrow-body commercial je... ver más
Revista: Infrastructures

 
Samiulhaq Wasiq and Amir Golroo    
Road networks play a significant role in each country?s economy, especially in countries such as Afghanistan, which is strategically located in the international transit path from Europe to East Asia. In such a country, pavement performance models are fu... ver más
Revista: Infrastructures

 
Khaled Arbateni and Amir Benzaoui    
Electrocardiography (ECG) is a simple and safe tool for detecting heart conditions. Despite the diaspora of existing heartbeat classifiers, improvements such as real-time heartbeat identification and patient-independent classification persist. Reservoir ... ver más
Revista: Applied Sciences

 
Tianhao Wang, Hongying Meng, Rui Qin, Fan Zhang and Asoke Kumar Nandi    
Wind turbines are a crucial part of renewable energy generation, and their reliable and efficient operation is paramount in ensuring clean energy availability. However, the bearings in wind turbines are subjected to high stress and loads, resulting in fa... ver más
Revista: Applied Sciences

 
Subin Kim, Heejin Hwang, Keunyeong Oh and Jiuk Shin    
The seismically deficient column details in existing reinforced concrete buildings affect the overall behavior of the building depending on the failure type of the column. The purpose of this study is to develop and validate a machine-learning-based pred... ver más
Revista: Applied Sciences