(k,p)-Planarity: A Relaxation of Hybrid Planarity

摘要

We present a new model for hybrid planarity that relaxes existing hybrid representations. 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: (ⅰ) each cluster is associated with a closed, bounded planar region, called a cluster region; (ⅱ) cluster regions are pairwise disjoint, (ⅲ) each vertex v ∈ V is identified with at most p distinct points, called ports, on the boundary of its cluster region; (ⅳ) each inter-cluster edge (u, v) ∈ E is identified with a Jordan arc connecting a port of u to a port of v; (ⅴ) inter-cluster edges do not cross or intersect cluster regions except at their endpoints. 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.