1 citations · 4 across the 13 of their papers we have counts for
16 papers
Garment numbers of bi-colored point sets in the plane
Oswin Aichholzer, Helena Bergold, Simon D. Fink +3
We consider colored variants of a class of geometric-combinatorial questions on -gons and empty -gons that have been started around 1935 by Erdős and Szekeres. In our setting…
Investigating Simple Drawings of using SAT
Helena Bergold, Manfred Scheucher
We present a SAT framework which allows to investigate properties of simple drawings of the complete graph using the power of AI. In contrast to classic imperative programmin…
On Triangular Separation of Bichromatic Point Sets
Helena Bergold, Arun Kumar Das, Robert Lauff +3
We address the problem of computing the minimum number of triangles to separate a set of blue points from a set of red points in . A set of triangles is a \emph{separ…
Signotopes with few plus signs
Helena Bergold, Lukas Egeling, Hung. P. Hoang
Arrangements of pseudohyperplanes are widely studied in computational geometry. A rich subclass of pseudohyerplane arrangements, which has gained more attention in recent years, is…
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…
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…
Using SAT to study plane Hamiltonian substructures in simple drawings
Helena Bergold, Stefan Felsner, Meghana M. Reddy +1
In 1988 Rafla conjectured that every simple drawing of a complete graph contains a plane, i.e., non-crossing, Hamiltonian cycle. The conjecture is far from being resolved. Th…
An extension theorem for signotopes
Helena Bergold, Stefan Felsner, Manfred Scheucher
In 1926, Levi showed that, for every pseudoline arrangement and two points in the plane, can be extended by a pseudoline which contains the two prescrib…
Well-Separation and Hyperplane Transversals in High Dimensions
Helena Bergold, Daniel Bertschinger, Nicolas Grelier +2
A family of point sets in dimensions is well-separated if the convex hulls of any two disjoint subfamilies can be separated by a hyperplane. Well-separation is a strong ass…
Colorings of oriented planar graphs avoiding a monochromatic subgraph
Helena Bergold, Winfried Hochstättler, Raphael Steiner
For a fixed simple digraph and a given simple digraph , an -free -coloring of is a vertex-coloring in which no induced copy of in is monochromatic. We stud…
The Neighborhood Polynomial of Chordal Graphs
Helena Bergold, Winfried Hochstättler, Uwe Mayer
We study the neighborhood polynomial and the complexity of its computation for chordal graphs. The neighborhood polynomial of a graph is the generating function of subsets of its v…
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…
A Semi-strong Perfect Digraph Theorem
Stephan Dominique Andres, Helena Bergold, Winfried Hochstättler +1
Reed showed that, if two graphs are -isomorphic, then either both are perfect or none of them is. In this note we will derive an analogous result for perfect digraphs.
On the Geometry of Holmsen's Combinatorial Version of the Colorful Carathéodory
Helena Bergold, Winfried Hochstättler
Carathéodorys Theorem of convex hulls plays an important role in convex geometry. In 1982, Bárány formulated and proved a more general version, called the Colorful Carathéodory. Th…