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

التفاصيل البيبلوغرافية
العنوان: (k,p)-Planarity: A Relaxation of Hybrid Planarity
المؤلفون: Di Giacomo, Emilio, Lenhart, William J., Liotta, Giuseppe, Randolph, Timothy W., Tappini, Alessandra
سنة النشر: 2018
المجموعة: Computer Science
مصطلحات موضوعية: Computer Science - Data Structures and Algorithms, Computer Science - Computational Complexity
الوصف: 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: (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 \in V$ is identified with at most $p$ distinct points, called \emph{ports}, on the boundary of its cluster region; (iv) each inter-cluster edge $(u,v) \in 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 endpoints. We first tightly bound the number of edges in a $(k,p)$-planar graph with $p
نوع الوثيقة: Working Paper
URL الوصول: http://arxiv.org/abs/1806.11413
رقم الأكسشن: edsarx.1806.11413
قاعدة البيانات: arXiv