Back to Search
Start Over
(k,p)-planarity: A relaxation of hybrid planarity.
- Source :
-
Theoretical Computer Science . Dec2021, Vol. 896, p19-30. 12p. - Publication Year :
- 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 ∈ 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) ∈ 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. [ABSTRACT FROM AUTHOR]
- Subjects :
- *PLANAR graphs
*NP-complete problems
*EDGES (Geometry)
Subjects
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 896
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 153477976
- Full Text :
- https://doi.org/10.1016/j.tcs.2021.09.044