24 citations · 124 across the 75 of their papers we have counts for
105 papers
Solving SAT via Treewidth Backdoors in Linear Time: Beyond Sparsity
Jan Dreier, Robert Ganian, Marlene Gründel +2
The Boolean Satisfiability (SAT) problem is a remarkably expressive computational problem, serving both as a cornerstone of complexity theory and as a unifying language for a wide…
Ramsey Meets Simultaneous Planarity: Vertex Integrity and Pathwidth
Thomas Depian, Simon D. Fink, Alexander Firbas +3
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 the…
A Uniform Algorithm for Strict NP on Bounded-Treedepth Graphs
Thomas Depian, Robert Ganian, Jakob Greilhuber +2
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; h…
Perfect Rectangular Tilings with Two Colors
Oswin Aichholzer, Robert Ganian, Phillip Keldenich +5
We study a finite tiling problem, where tiles are unit squares whose four edges are colored with one of two colors. We ask whether a given rectangle admits a perfect rectangular ti…
The (Parameterized) Complexity of Ordering a Graph While Avoiding a Forbidden Pattern
Thomas Depian, Simon D. Fink, Alexander Firbas +3
In this paper, we study the Pattern Avoidance problem of determining whether a given graph admits a linear vertex order which avoids a given pattern , i.e., a vertex sequenc…
Not All Degree Constraints Are Created Equal when Computing Spanning Trees
Narek Bojikian, Alexander Firbas, Robert Ganian +2
We study the computation of minimum spanning trees subject to local degree constraints. Recent work (ICALP 2026) established that three natural formalizations of this problem share…