3 papers
cs.CC2024
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…
math.CO2023
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…
cs.CG2023
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…