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

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.