We present a new model for hybrid planarity that relaxes existing hybrid representation models. A graph G = (V, E) is (k, p)-planar if V can be partitioned into clusters of size at most k such that G admits a drawing where: (i) each cluster is associated with a closed, bounded planar region, called a cluster region; (ii) cluster regions are pairwise disjoint, (iii) each vertex v is an element of V is identified with at most p distinct points, called ports, on the boundary of its cluster region; (iv) each inter-cluster edge (u, v) is an element of E is identified with a Jordan arc connecting a port of u to a port of v; (v) inter-cluster edges do not cross or intersect cluster regions except at their end-points. We first tightly bound the number of edges in a (k, p)-planar graph with p < k. We then prove that (4, 1)-planarity testing and (2, 2)-planarity testing are NP-complete problems. Finally, we prove that neither the class of (2, 2)-planar graphs nor the class of 1-planar graphs contains the other, indicating that the (k, p)-planar graphs are a large and novel class. (C) 2021 Elsevier B.V. All rights reserved.

(k, p)-planarity: A relaxation of hybrid planarity

Di Giacomo, E;Liotta, G;Tappini, A
2021

Abstract

We present a new model for hybrid planarity that relaxes existing hybrid representation models. A graph G = (V, E) is (k, p)-planar if V can be partitioned into clusters of size at most k such that G admits a drawing where: (i) each cluster is associated with a closed, bounded planar region, called a cluster region; (ii) cluster regions are pairwise disjoint, (iii) each vertex v is an element of V is identified with at most p distinct points, called ports, on the boundary of its cluster region; (iv) each inter-cluster edge (u, v) is an element of E is identified with a Jordan arc connecting a port of u to a port of v; (v) inter-cluster edges do not cross or intersect cluster regions except at their end-points. We first tightly bound the number of edges in a (k, p)-planar graph with p < k. We then prove that (4, 1)-planarity testing and (2, 2)-planarity testing are NP-complete problems. Finally, we prove that neither the class of (2, 2)-planar graphs nor the class of 1-planar graphs contains the other, indicating that the (k, p)-planar graphs are a large and novel class. (C) 2021 Elsevier B.V. All rights reserved.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11391/1532755
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact