11 citations · 33 across the 21 of their papers we have counts for
5 papers · 1 filter
Subgraph-universal planar graphs for trees
Helena Bergold, Vesna Iršič, Robert Lauff +3
We show that there exists an outerplanar graph on vertices for that contains every tree on vertices as a subgraph. This exten…
Holes in Convex and Simple Drawings
Helena Bergold, Joachim Orthaber, Manfred Scheucher +1
Gons and holes in point sets have been extensively studied in the literature. For simple drawings of the complete graph a generalization of the Erdős--Szekeres theorem is known and…
An Improved Lower Bound on the Number of Pseudoline Arrangements
Fernando Cortés Kühnast, Justin Dallant, Stefan Felsner +1
Arrangements of pseudolines are classic objects in discrete and computational geometry. They have been studied with increasing intensity since their introduction almost 100 years a…
Plane Hamiltonian Cycles in Convex Drawings
Helena Bergold, Stefan Felsner, Meghana M. Reddy +2
A conjecture by Rafla from 1988 asserts that every simple drawing of the complete graph admits a plane Hamiltonian cycle. It turned out that already the existence of much sim…
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…