26 citations · 28 across the 5 of their papers we have counts for
8 papers
Finding hardness reductions automatically using SAT solvers
Helena Bergold, Manfred Scheucher, Felix Schröder
In this article, we show that the completion problem, i.e. the decision problem whether a partial structure can be completed to a full structure, is NP-complete for many combinator…
The Density Formula: One Lemma to Bound Them All
Michael Kaufmann, Boris Klemz, Kristin Knorr +3
We introduce the Density Formula for (topological) drawings of graphs in the plane or on the sphere, which relates the number of edges, vertices, crossings, and sizes of cells in t…
Linear Size Universal Point Sets for Classes of Planar Graphs
Stefan Felsner, Hendrik Schrezenmaier, Felix Schröder +1
A finite set of points in the plane is -universal with respect to a class of planar graphs if every -vertex graph in admits a crossing-free st…
Characterization of matrices with bounded Graver bases and depth parameters and applications to integer programming
Marcin Brianski, Martin Koutecky, Daniel Kral +2
An intensive line of research on fixed parameter tractability of integer programming is focused on exploiting the relation between the sparsity of a constraint matrix and the n…
Coloring Drawings of Graphs
Christoph Hertrich, Felix Schröder, Raphael Steiner
We consider cell colorings of drawings of graphs in the plane. Given a multi-graph together with a drawing in the plane with only finitely many crossings, we define a ce…
Topological Drawings meet Classical Theorems from Convex Geometry
Helena Bergold, Stefan Felsner, Manfred Scheucher +2
In this article we discuss classical theorems from Convex Geometry in the context of topological drawings and beyond. In a simple topological drawing of the complete graph , a…
Improved bounds for centered colorings
Michał Dębski, Stefan Felsner, Piotr Micek +1
A vertex coloring of a graph is -centered if for every connected subgraph of either uses more than colors on or there is a color that appears exactly…
On the Complexity of Digraph Colourings and Vertex Arboricity
Winfried Hochstättler, Felix Schröder, Raphael Steiner
It has been shown by Bokal et al. that deciding 2-colourability of digraphs is an NP-complete problem. This result was later on extended by Feder et al. to prove that deciding whet…