Abstract A matchstick graph is a plane graph with edges drawn as unit-distance line segments. Harborth introduced these graphs in 1981 and conjectured that the maximum number of edges for a matchstick graph on n vertices is $$\lfloor 3n-\sqrt{12n-3}\rfloor $$ ⌊ 3 n - 12 n - 3 ⌋ . In this paper we prove this conjecture for all $$n\ge 1$$ n ≥ 1 . The main geometric ingredient of the proof is an isoperimetric inequality related to L’Huilier’s inequality.

A matchstick graph is a crossing-free unit-distance graph in the plane. Harborth conjectured in 1981 that the maximum number of edges of a matchstick graph with $n$ vertices is $\lfloor 3n-\sqrt{12n-3}\rfloor$. Using the Euler formula and the isoperimetric inequality, it can be shown that a matchstick graph with $n$ vertices has no more than $3n-\sqrt{2\pi\sqrt{3}\cdot n}+O(1)$ edges. We improve this upper bound to $3n-c\sqrt{n-1/4}$ edges, where $c=\frac12(\sqrt{12} + \sqrt{2\pi\sqrt{3}})$. The main tool in the proof is a new upper bound for the number of edges that takes into account the number of nontriangular faces. We also find a sharp upper bound for the number of triangular faces in a matchstick graph.

An ordinary circle of a set P of n points in the plane is defined as a circle that contains exactly three points of P. We show that if P is not contained in a line or a circle, then P spans at least $$n^2/4 - O(n)$$ ordinary circles. Moreover, we determine the exact minimum number of ordinary circles for all sufficiently large n and describe all point sets that come close to this minimum. We also consider the circle variant of the orchard problem. We prove that P spans at most $$n^3/24 - O(n^2)$$ circles passing through exactly four points of P. Here we determine the exact maximum and the extremal configurations for all sufficiently large n. These results are based on the following structure theorem. If n is sufficiently large depending on K, and P is a set of n points spanning at most $$Kn^2$$ ordinary circles, then all but O(K) points of P lie on an algebraic curve of degree at most four. Our proofs rely on a recent result of Green and Tao on ordinary lines, combined with circular inversion and some classical results regarding algebraic curves.

Abstract We investigate the problem of designing a minimum‐cost flow network interconnecting n sources and a single sink, each with known locations in a normed space and with associated flow demands. The network may contain any finite number of additional unprescribed nodes from the space; these are known as the Steiner points. For concave increasing cost functions, a minimum‐cost network of this sort has a tree topology, and hence can be called a Minimum Gilbert Arborescence (MGA). We characterize the local topological structure of Steiner points in MGAs, showing, in particular, that for a wide range of metrics, and for some typical real‐world cost functions, the degree of each Steiner point is 3. © 2012 Wiley Periodicals, Inc. NETWORKS, 2013

We present some elementary ideas to prove the following Sylvester–Gallai type theorems involving incidences between points and lines in the planes over the complex numbers and quaternions. 1. Let A and B be finite sets of at least two complex numbers each. Then there exists a line $\ell$ in the complex affine plane such that $\lvert(A\times B)\cap\ell\rvert=2$. 2. Let S be a finite noncollinear set of points in the complex affine plane. Then there exists a line $\ell$ such that $2\leq \lvert S\cap\ell\rvert \leq 5$. 3. Let A and B be finite sets of at least two quaternions each. Then there exists a line $\ell$ in the quaternionic affine plane such that $2\leq \lvert(A\times B)\cap\ell\rvert \leq 5$. 4. Let S be a finite noncollinear set of points in the quaternionic affine plane. Then there exists a line $\ell$ such that $2\leq \lvert S\cap\ell\rvert \leq 24$.

We present a geometric analysis of the local structure of vertices in a Steiner minimum tree in an arbitrary normed plane in terms of so-called absorbing and critical angles, thereby unifying various results known for specific norms. We find necessary and sufficient conditions for a set of segments emanating from a point to be the neighborhood of a vertex in a Steiner minimum tree. As corollaries, we show that the maximum possible degree of a Steiner point and of a given point are equal, and equal 3 or 4, except if the unit ball is an affine regular hexagon, where it is known that the maximum degree of a Steiner point is 4 and of a regular point is 6. We also characterize the planes where the maximum degree is 4, the so-called X-planes, and present examples. In particular, if the unit ball is an affine regular 2n-gon, Steiner points of degree 4 exist if and only if n = 2, 3, 4, or 6. © 2000 John Wiley & Sons, Inc.