1 citations · 1 across the 6 of their papers we have counts for
9 papers
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…
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…
Two-Layer Drawings with a Tree on Top: Vertex Splits and Fixed-Parameter Algorithms
Alexander Firbas, Robert Ganian, Sylvain Meunier +1
Two-layer drawings of bipartite graphs place the vertices of each part on one of two parallel lines and draw the edges as straight-line links. Traditionally, the optimization goal…
The Parameterized Complexity of Geometric 1-Planarity
Alexander Firbas
A graph is geometric 1-planar if it admits a straight-line drawing where each edge is crossed at most once. We provide the first systematic study of the parameterized complexity of…
Fine-Grained Complexity of Computing Degree-Constrained Spanning Trees
Narek Bojikian, Alexander Firbas, Robert Ganian +2
We investigate the computation of minimum-cost spanning trees satisfying prescribed vertex degree constraints: Given a graph and a constraint function , we ask for a (minimu…
Pathways to Tractability for Geometric Thickness
Thomas Depian, Simon Dominik Fink, Alexander Firbas +2
We study the classical problem of computing geometric thickness, i.e., finding a straight-line drawing of an input graph and a partition of its edges into as few parts as possible…
On the Complexity of Establishing Hereditary Graph Properties via Vertex Splitting
Alexander Firbas, Manuel Sorge
Vertex splitting is a graph operation that replaces a vertex with two nonadjacent new vertices and makes each neighbor of adjacent with one or both of the introduced vertic…
The Complexity of Cluster Vertex Splitting and Company
Alexander Firbas, Alexander Dobler, Fabian Holzer +4
Clustering a graph when the clusters can overlap can be seen from three different angles: We may look for cliques that cover the edges of the graph with bounded overlap, we may loo…