(k,p)-Planarity: A Generalization of Hybrid Planarity
share
A graph G is (k,p)-planar if its vertices 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 region in the plane (called cluster region) that is topologically equivalent to a disk; (ii) Cluster regions are pairwise disjoint; (iii) Each vertex of a cluster is associated with at most p distinct points (called ports) on the boundary of its cluster region; (iv) Each edge (u,v) is a Jordan arc connecting a port of u with a port of v; and (v) Edges connecting different clusters do not cross each other and do not intersect any cluster region, with the only exception for end-points. We first ask a Turán-type question and give a tight upper bound on the number of edges of (k,p)-planar graphs. We then study the complexity of the (k,p)-planarity testing problem and prove that (4,1)-planarity testing and (2,2)-planarity testing are both NP-complete problems. Finally, motivated by the NP-completeness of (2,2)-planarity testing, we investigate the combinatorial properties of (2,2)-planar graphs and study their relationship with 1-planar graphs, describing families of 1-planar graphs that are (2,2)-planar as well as families that are not.
READ FULL TEXT