M. de Berg

activity

20072026

most citedIndependent Set Reconfiguration Thresholds of Hereditary Graph Classes

10 citations · 18 across the 13 of their papers we have counts for

collaborators

Showing 2017Show all

3 papers · 1 filter

cs.CG2017

Minimum Perimeter-Sum Partitions in the Plane

Mikkel Abrahamsen, Mark de Berg, Kevin Buchin +2

Let $P$ be a set of $n$ points in the plane. We consider the problem of partitioning $P$ into two subsets $P_{1}$ and $P_{2}$ such that the sum of the perimeters of $CH (P_{1})$ an…

cs.CG2017

Fully-Dynamic and Kinetic Conflict-Free Coloring of Intervals with Respect to Points

Mark de Berg, Tim Leijsen, André van Renssen +3

We introduce the fully-dynamic conflict-free coloring problem for a set $S$ of intervals in $R^{1}$ with respect to points, where the goal is to maintain a conflict-free col…

cs.CG2017

Removing Depth-Order Cycles Among Triangles: An Efficient Algorithm Generating Triangular Fragments

Mark de Berg

More than 25 years ago Chazelle~\emph{et al.} (FOCS 1991) studied the following question: Is it possible to cut any set of $n$ lines in $R^{3}$ into a subquadratic number of f…