We study the following simultaneous embedding problem: Given k graphs on the same vertex set with the same pairwise intersection, do they admit planar drawings that coincide on their shared graph? We establish fixed-parameter tractability with respect to the vertex integrity of the union graph (that is, the union of th...
Thomas Depian, S. D. Fink, Alexander Firbas et al.· 0 citations
A classical well-quasi-ordering result guarantees the existence of non-uniform linear-time algorithms for all problems in Strict NP on relational structures of bounded treedepth; however, this provides neither a procedure for constructing these algorithms nor computable bounds on their parameter dependence. We turn thi...
Thomas Depian, Robert Ganian, Jakob Greilhuber et al.· 0 citations
This paper studies the more general embeddability question where the placement of each vertex is restricted to a list of admissible points, and shows NP-hardness for bi-labeled paths.
Thomas Depian, Joseph Dorfer, Boris Klemz et al.· arXiv.org· 0 citations
It is shown that Pattern Avoidance is $\Sigma_2^{\textsf{P}}$-complete and furthermore remains intractable (in both the classical and parameterized sense) even under a variety of severe restrictions to both the pattern $P$ and the graph $G$.
Thomas Depian, S. D. Fink, Alexander Firbas et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
