HUEMER , Clemens

Problem 50 in the Open Problems Project asks whether any triangulation on a point set in the plane contains a pointed spanning tree as a subgraph. We provide a counterexample. As a consequence we show that there exist triangulations which require a linear number of edge flips to become Hamiltonian.

The Fiedler value λ_2, also known as algebraic connectivity, is the second smallest Laplacian eigenvalue of a graph. We study the maximum Fiedler value among all planar graphs G with n vertices, denoted by λ_2max, and we show the bounds 2+\Theta(1/n^2) \leq λ_2max \leq 2+O(1/n). We also provide bounds on the maximum Fiedler value for the...

The Fiedler value λ_2, also known as algebraic connectivity, is the second smallest Laplacian eigenvalue of a graph. We study the maximum Fiedler value among all planar graphs G with n vertices, denoted by λ_2max, and we show the bounds 2+\Theta(1/n^2) \leq λ_2max \leq 2+O(1/n). We also provide bounds on the maximum Fiedler value for the...

Let S be a two-colored set of n points in general position in the plane. We show that S admits at least 2 n 17 pairwise disjoint monochromatic triangles with vertices in S and empty of points of S. We further show that S can be partitioned into 3 n 11 subsets with pairwise disjoint convex hull such that within each subset all but at...

In 1979 Conway, Croft, Erd\H{o}s and Guy proved that every set SS of nn points in general position in the plane determines at least n3/18−O(n2) obtuse angles and also presented a special set of nn points to show the upper bound 2n3/27−O(n2) on the minimum number of obtuse angles among all sets SS. We prove that every set SS of nn points in...

Given a set S of n points in the plane, in this paper we give a necessary and sometimes sufficient condition to build a 4-connected non-crossing geometric graph on S.

No description