Advancements on SEFE and Partitioned Book Embedding problems

Autor: Patrizio Angelini, Daniel Neuwirth, Giordano Da Lozzo
Přispěvatelé: Angelini, Patrizio, DA LOZZO, Giordano, Daniel, Neuwirth
Rok vydání: 2015
Předmět:
Zdroj: Theoretical Computer Science. 575:71-89
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2014.11.016
Popis: In this work we investigate the complexity of some problems related to the {\em Simultaneous Embedding with Fixed Edges} (SEFE) of $k$ planar graphs and the PARTITIONED $k$-PAGE BOOK EMBEDDING (PBE-$k$) problems, which are known to be equivalent under certain conditions. While the computational complexity of SEFE for $k=2$ is still a central open question in Graph Drawing, the problem is NP-complete for $k \geq 3$ [Gassner {\em et al.}, WG '06], even if the intersection graph is the same for each pair of graphs ({\em sunflower intersection}) [Schaefer, JGAA (2013)]. We improve on these results by proving that SEFE with $k \geq 3$ and sunflower intersection is NP-complete even when the intersection graph is a tree and all the input graphs are biconnected. Also, we prove NP-completeness for $k \geq 3$ of problem PBE-$k$ and of problem PARTITIONED T-COHERENT $k$-PAGE BOOK EMBEDDING (PTBE-$k$) - that is the generalization of PBE-$k$ in which the ordering of the vertices on the spine is constrained by a tree $T$ - even when two input graphs are biconnected. Further, we provide a linear-time algorithm for PTBE-$k$ when $k-1$ pages are assigned a connected graph. Finally, we prove that the problem of maximizing the number of edges that are drawn the same in a SEFE of two graphs is NP-complete in several restricted settings ({\em optimization version of SEFE}, Open Problem $9$, Chapter $11$ of the Handbook of Graph Drawing and Visualization).
29 pages, 10 figures, extended version of 'On Some NP-complete SEFE Problems' (Eighth International Workshop on Algorithms and Computation, 2014)
Databáze: OpenAIRE
Externí odkaz: