科研之友
微信
新浪微博
Facebook
分享链接
摘要
In this work we investigate the complexity of some combinatorial problems related to the Simultaneous Embedding with Fixed Edges (SEFE) and the PARTITIONED T-COHERENT k-PAGE BOOK EMBEDDING (PTBE-k) problems, which are known to be equivalent under certain conditions. Given k planar graphs on the same set of n vertices, the SEFE problem asks to find a drawing of each graph on the same set of n points in such a way that each edge that is common to more than one graph is represented by the same curve in the drawings of all such graphs. Given a tree T with n leaves and a collection of k edge-sets E-i connecting pairs of leaves of T, the PTBE-k problem asks to find an ordering O of the leaves of T that is represented by T such that the endvertices of two edges in any set E-i do not alternate in O. The SEFE problem is NP-complete for k >= 3 even if the intersection graph is the same for each pair of graphs (sunflower intersection). We prove that this is true even when the intersection graph is a tree and all the input graphs are biconnected. This result implies the NP-completeness of PTBE-k for k >= 3. However, we prove stronger results on this problem, namely that PTBE-k remains NP-complete for k >= 3 even if (i) two of the input graphs G(i) = T U E-i are biconnected and T is a caterpillar or if (ii) T is a star. This latter setting is also known in the literature as PARTITIONED k-PAGE Book EMBEDDING. On the positive side, we provide a linear-time algorithm for PTBE-k when all but one of the edge-sets induce connected graphs. Finally, we prove that the problem of maximizing the number of edges that are drawn the same in a SEFE of two graphs (optimization of SEFE) is NP-complete, even in several restricted settings.
- 出版日期2015-4-13
