15 citations · 21 across the 8 of their papers we have counts for
12 papers
On Connectivity in Random Graph Models with Limited Dependencies
Johannes Lengler, Anders Martinsson, Kalina Petrova +4
For any positive edge density , a random graph in the Erdős-Renyi model is connected with non-zero probability, since all edges are mutually independent. We consider r…
Clustering under Perturbation Stability in Near-Linear Time
Pankaj K. Agarwal, Hsien-Chih Chang, Kamesh Munagala +2
We consider the problem of center-based clustering in low-dimensional Euclidean spaces under the perturbation stability assumption. An instance is -stable if the underlying opti…
Connectivity of Triangulation Flip Graphs in the Plane
Uli Wagner, Emo Welzl
Given a finite point set P in general position in the plane, a full triangulation is a maximal straight-line embedded plane graph on P. A partial triangulation is a full triangulat…
Convex Hulls of Random Order Types
Xavier Goaoc, Emo Welzl
We establish the following two main results on order types of points in general position in the plane (realizable simple planar order types, realizable uniform acyclic oriented mat…
Minimal Representations of Order Types by Geometric Graphs
Oswin Aichholzer, Martin Balko, Michael Hoffmann +8
In order to have a compact visualization of the order type of a given point set S, we are interested in geometric graphs on S with few edges that unambiguously display the order ty…
From Crossing-Free Graphs on Wheel Sets to Embracing Simplices and Polytopes with Few Vertices
Alexander Pilz, Emo Welzl, Manuel Wettstein
A set of points in general position in the plane is called a wheel set if all points but are extreme. We show that for the purpose of counting crossing…