Search

We prove that, for every set of $n$ points $\mathcal{P}$ in $\mathbb{R}^2$, a random plane graph drawn on $\mathcal{P}$ is expected to contain less than $n/10.18$ isolated vertices. In the other direction, we construct a point set where the expected number of isolated vertices in a random plane graph is about $n/23.32$. For $i\ge 1$, we prove that the expected number of vertices of degree $i$ is always less than $n/\sqrt{\pi i}$ Our analysis is based on cross-graph charging schemes. That is, we move charge between vertices from different plane graphs of the same point set. This leads to information about the expected behavior of a random plane graph.

The expansion of bivariate polynomials is well-understood for sets with a linear-sized product set. In contrast, not much is known for sets with small sumset. In this work, we provide expansion bounds for polynomials of the form $f(x, y) = g(x + p(y)) + h(y)$ for sets with small sumset. In particular, we prove that when $|A|$, $|B|$, $|A + A|$, and $|B + B|$ are not too far apart, for every $\varepsilon > 0$ we have \[|f(A, B)| = \Omega\left(\frac{|A|^{256/121 - \varepsilon}|B|^{74/121 - \varepsilon}}{|A + A|^{108/121}|B + B|^{24/121}}\right).\] We show that the above bound and its variants have a variety of applications in additive combinatorics and distinct distances problems. Our proof technique relies on the recent proximity approach of Solymosi and Zahl. In particular, we show how to incorporate the size of a sumset into this approach.

We completely characterize point--line configurations with $\Theta(n^{4/3})$ incidences when the point set is a section of the integer lattice. This can be seen as the main special case of the structural Szemer\'edi-Trotter problem. We also derive a partial characterization for several generalizations: (i) We rule out the concurrent lines case when the point set is a Cartesian product of an arithmetic progression and an arbitrary set. (ii) We study the case of a Cartesian product where one or both sets are generalized arithmetic progression. Our proofs rely on deriving properties of multiplicative energies.

We study the minimum number of distinct distances between point sets on two curves in $R^3$. Assume that one curve contains $m$ points and the other $n$ points. Our main results: (a) When the curves are conic sections, we characterize all cases where the number of distances is $O(m+n)$. This includes new constructions for points on two parabolas, two ellipses, and one ellipse and one hyperbola. In all other cases, the number of distances is $\Omega(\min\{m^{2/3}n^{2/3},m^2,n^2\})$. (b) When the curves are not necessarily algebraic but smooth and contained in perpendicular planes, we characterize all cases where the number of distances is $O(m+n)$. This includes a surprising new construction of non-algebraic curves that involve logarithms. In all other cases, the number of distances is $\Omega(\min\{m^{2/3}n^{2/3},m^2,n^2\})$.

We study a lower bound for the constant of the Szemer\'edi-Trotter theorem. In particular, we show that a recent infinite family of point-line configurations satisfies $I({\mathcal P},{\mathcal L})\ge (c+o(1)) |{\mathcal P}|^{2/3}|{\mathcal L}|^{2/3}$, with $c\approx 1.27$. Our technique is based on studying a variety of properties of Euler's totient function. We also improve the current best constant for Elekes's construction from 1 to about 1.27. From an expository perspective, this is the first full analysis of the constant of Erd\H os's construction.

We study configurations of $n$ points and $n$ lines that form $\Theta(n^{4/3})$ incidences, when the point set is a Cartesian product. We prove structural properties of such configurations, such that there exist many families of parallel lines or many families of concurrent lines. We show that the line slopes have multiplicative structure or that many sets of $y$-intercepts have additive structure. We introduce the first infinite family of configurations with $\Theta(n^{4/3})$ incidences. We also derive a new variant of a different structural point-line result of Elekes. Our techniques are based on the concept of line energy. Recently, Rudnev and Shkredov introduced this energy and showed how it is connected to point-line incidences. We also prove that their bound is tight up to sub-polynomial factors.

We improve the current best bound for distinct distances on non-ruled algebraic surfaces in ${\mathbb R}^3$. In particular, we show that $n$ points on such a surface span $\Omega\left(n^{32/39-\varepsilon}\right)$ distinct distances, for any $\varepsilon>0$. Our proof adapts the proof of Sz\'ekely for the planar case, which is based on the crossing lemma. As part of our proof for distinct distances on surfaces, we also obtain new results for distinct distances between circles in ${\mathbb R}^3$. Consider point sets ${\mathcal P}_1$ and ${\mathcal P}_2$ of respective sizes $m$ and $n$, such that each set lies on a distinct circle in ${\mathbb R}^3$. We characterize the cases when the number of distinct distances between the two sets can be $O(m+n)$. This includes a new configuration with a small number of distances. In any other case, we prove that the number of distinct distances is $\Omega\left(\min\left\{m^{2/3}n^{2/3},m^2,n^2\right\}\right)$.

We prove that if $P$ is a set of $n$ points in $\mathbb{C}^2$, then either the points in $P$ determine $\Omega(n^{1-\epsilon})$ complex distances, or $P$ is contained in a line with slope $\pm i$. If the latter occurs then each pair of points in $P$ have complex distance 0., Comment: 41 pages, 0 figures

We study a generalization of Erd\H os's unit distances problem to chains of $k$ distances. Given $\mathcal P,$ a set of $n$ points, and a sequence of distances $(\delta_1,\ldots,\delta_k)$, we study the maximum possible number of tuples of distinct points $(p_1,\ldots,p_{k+1})\in \mathcal P^{k+1}$ satisfying $|p_j p_{j+1}|=\delta_j$ for every $1\leq j \leq k$. We study the problem in $\mathbb R^2$ and in $\mathbb R^3$, and derive upper and lower bounds for this family of problems., Comment: 9 pages, 1 figure

We study the sum-product problem for the planar hypercomplex numbers: the dual numbers and double numbers. These number systems are similar to the complex numbers, but it turns out that they have a very different combinatorial behavior. We identify parameters that control the behavior of these problems, and derive sum-product bounds that depend on these parameters. For the dual numbers we expose a range where the minimum value of $\max\{|A+A|,|AA|\}$ is neither close to $|A|$ nor to $|A|^2$. To obtain our main sum-product bound, we extend Elekes' sum-product technique that relies on point-line incidences. Our extension is significantly more involved than the original proof, and in some sense runs the original technique a few times in a bootstrapping manner. We also study point-line incidences in the dual plane and in the double plane, developing analogs of the Szemeredi-Trotter theorem. As in the case of the sum-product problem, it turns out that the dual and double variants behave differently than the complex and real ones.

We construct finite sets of real numbers that have a small difference set and strong local properties. In particular, we construct a set $A$ of $n$ real numbers such that $|A-A|=n^{\log_2 3}$ and that every subset $A'\subseteq A$ of size $k$ satisfies $|A'-A'|\ge k^{\log_2 3}$. This construction leads to the first non-trivial upper bound for the problem of distinct distances with local properties.

The local properties problem of Erd\H{o}s and Shelah generalizes many Ramsey problems and some distinct distances problems. In this work, we derive a variety of new bounds for the local properties problem and its variants. We do this by continuing to develop the color energy technique --- a variant of the concept of additive energy from Additive Combinatorics. In particular, we generalize the concept of color energy to higher color energies, and combine these with Extremal Graph Theory results about graphs with no cycles or subdivisions of size $k$.

We study Extremal Combinatorics problems where local properties are used to derive global properties. That is, we consider a given configuration where every small piece of the configuration satisfies some restriction, and use this local property to derive global properties of the entire configuration. We study one such Ramsey problem of Erd\H{o}s and Shelah, where the configurations are complete graphs with colored edges and every small induced subgraph contains many distinct colors. Our bounds for this Ramsey problem show that the known probabilistic construction is tight in various cases. We study one Discrete Geometry variant, also by Erd\H{o}s, where we have a set of points in the plane such that every small subset spans many distinct distances. Finally, we consider an Additive Combinatorics problem, where we are given sets of real numbers such that every small subset has a large difference set. We derive new bounds for all of the above problems. Our proof technique is based on introducing an non-algebraic variant of additive energies. This abstract energy variant is based on edge colors in graphs., Comment: Subsumes part of arXiv:1709.06696. To appear in Combinatorica

We derive a general upper bound for the number of incidences with $k$-dimensional varieties in ${\mathbb R}^d$. The leading term of this new bound generalizes previous bounds for the special cases of $k=1, k=d-1,$ and $k= d/2$, to every $1\le k

We adapt the idea of higher moment energies, originally used in Additive Combinatorics, so that it would apply to problems in Discrete Geometry. This new approach leads to a variety of new results, such as (i) Improved bounds for the problem of distinct distances with local properties. (ii) Improved bounds for problems involving expanding polynomials in ${\mathbb R}[x,y]$ (Elekes-Ronyai type bounds) when one or two of the sets have structure. Higher moment energies seem to be related to additional problems in Discrete Geometry, to lead to new elegant theory, and to raise new questions.

We introduce a reduction from the distinct distances problem in ${\mathbb R}^d$ to an incidence problem with $(d-1)$-flats in ${\mathbb R}^{2d-1}$. Deriving the conjectured bound for this incidence problem (the bound predicted by the polynomial partitioning technique) would lead to a tight bound for the distinct distances problem in ${\mathbb R}^d$. The reduction provides a large amount of information about the $(d-1)$-flats, and a framework for deriving more restrictions that these satisfy. Our reduction is based on introducing a Lie group that is a double cover of the special Euclidean group. This group can be seen as a variant of the Spin group, and a large part of our analysis involves studying its properties., Comment: To appear in Journal of Combinatorial Theory series A. In the second revision, Section 7 was added

We prove that the number of incidences between $m$ points and $n$ bounded-degree curves with $k$ degrees of freedom in ${\mathbb R}^d$ is \[ I(m,n) =O\left(m^{\frac{k}{dk-d+1}+\varepsilon}n^{\frac{dk-d}{dk-d+1}}+ \sum_{j=2}^{d-1} m^{\frac{k}{jk-j+1}+\varepsilon}n^{\frac{d(j-1)(k-1)}{(d-1)(jk-j+1)}}q_j^{\frac{(d-j)(k-1)}{(d-1)(jk-j+1)}}+m+n\right), \] for any $\varepsilon>0$, where the constant of proportionality depends on $k, \varepsilon$ and $d$, provided that no $j$-dimensional surface of degree $\le c_j(k,d,\varepsilon)$, a constant parameter depending on $k$, $d$, $j$, and $\varepsilon$, contains more than $q_j$ input curves, and that the $q_j$'s satisfy certain mild conditions. This bound generalizes a recent result of Sharir and Solomon concerning point-line incidences in four dimensions (where $d=4$ and $k=2$), and partly generalizes a recent result of Guth (as well as the earlier bound of Guth and Katz) in three dimensions (Guth's three-dimensional bound has a better dependency on $q_2$). It also improves a recent $d$-dimensional general incidence bound by Fox, Pach, Sheffer, Suk, and Zahl, in the special case of incidences with algebraic curves. Our results are also related to recent works by Dvir and Gopi and by Hablicsek and Scherr concerning rich lines in high-dimensional spaces.

We present a technique for deriving lower bounds for incidences with hypersurfaces in ${\mathbb R}^d$ with $d\ge 4$. These bounds apply to a large variety of hypersurfaces, such as hyperplanes, hyperspheres, paraboloids, and hypersurfaces of any degree. Beyond being the first non-trivial lower bounds for various incidence problems, our bounds show that some of the known upper bounds for incidence problems in ${\mathbb R}^d$ are tight up to an extra $\varepsilon$ in the exponent. Specifically, for every $m$, $d\ge 4$, and $\varepsilon>0$ there exist $m$ points and $n$ hypersurfaces in ${\mathbb R}^d$ (where $n$ depends on $m$) with no $K_{2,\frac{d-1}{\varepsilon}}$ in the incidence graph and $\Omega\left(m^{(2d-2)/(2d-1)}n^{d/(2d-1)-\varepsilon} \right)$ incidences. Moreover, we provide improved lower bounds for the case of no $K_{s,s}$ in the incidence graph, for large constants $s$. Our analysis builds upon ideas from a recent work of Bourgain and Demeter on discrete Fourier restriction to the four- and five-dimensional spheres. Specifically, it is based on studying the additive energy of the integer points in a truncated paraboloid.

Domino tileability is a classical problem in Discrete Geometry, famously solved by Thurston for simply connected regions in nearly linear time in the area. In this paper, we improve upon Thurston's height function approach to a nearly linear time in the perimeter., Comment: Appeared in Discrete Comput. Geom. 56 (2016), 377-394

We prove an incidence theorem for points and curves in the complex plane. Given a set of $m$ points in ${\mathbb R}^2$ and a set of $n$ curves with $k$ degrees of freedom, Pach and Sharir proved that the number of point-curve incidences is $O\big(m^{\frac{k}{2k-1}}n^{\frac{2k-2}{2k-1}}+m+n\big)$. We establish the slightly weaker bound $O_\varepsilon\big(m^{\frac{k}{2k-1}+\varepsilon}n^{\frac{2k-2}{2k-1}}+m+n\big)$ on the number of incidences between $m$ points and $n$ (complex) algebraic curves in ${\mathbb C}^2$ with $k$ degrees of freedom. We combine tools from algebraic geometry and differential geometry to prove a key technical lemma that controls the number of complex curves that can be contained inside a real hypersurface. This lemma may be of independent interest to other researchers proving incidence theorems over ${\mathbb C}$., Comment: The proof was significantly simplified, and now relies on the Picard-Lindelof theorem, rather than on foliations

We introduce the bisector energy of an $n$-point set $P$ in $\mathbb{R}^2$, defined as the number of quadruples $(a,b,c,d)$ from $P$ such that $a$ and $b$ determine the same perpendicular bisector as $c$ and $d$. If no line or circle contains $M(n)$ points of $P$, then we prove that the bisector energy is $O(M(n)^{\frac{2}{5}}n^{\frac{12}{5}+\epsilon} + M(n)n^2).$. We also prove the lower bound $\Omega(M(n)n^2)$, which matches our upper bound when $M(n)$ is large. We use our upper bound on the bisector energy to obtain two rather different results: (i) If $P$ determines $O(n/\sqrt{\log n})$ distinct distances, then for any $0<\alpha\le 1/4$, either there exists a line or circle that contains $n^\alpha$ points of $P$, or there exist $\Omega(n^{8/5-12\alpha/5-\epsilon})$ distinct lines that contain $\Omega(\sqrt{\log n})$ points of $P$. This result provides new information on a conjecture of Erd\H{o}s regarding the structure of point sets with few distinct distances. (ii) If no line or circle contains $M(n)$ points of $P$, then the number of distinct perpendicular bisectors determined by $P$ is $\Omega(\min\{M(n)^{-2/5}n^{8/5-\epsilon}, M(n)^{-1} n^2\})$. This appears to be the first higher-dimensional example in a framework for studying the expansion properties of polynomials and rational functions over $\mathbb{R}$, initiated by Elekes and R\'onyai., Comment: 18 pages, 2 figures

A bipartite graph $G$ is semi-algebraic in $\mathbb{R}^d$ if its vertices are represented by point sets $P,Q \subset \mathbb{R}^d$ and its edges are defined as pairs of points $(p,q) \in P\times Q$ that satisfy a Boolean combination of a fixed number of polynomial equations and inequalities in $2d$ coordinates. We show that for fixed $k$, the maximum number of edges in a $K_{k,k}$-free semi-algebraic bipartite graph $G = (P,Q,E)$ in $\mathbb{R}^2$ with $|P| = m$ and $|Q| = n$ is at most $O((mn)^{2/3} + m + n)$, and this bound is tight. In dimensions $d \geq 3$, we show that all such semi-algebraic graphs have at most $C\left((mn)^{ \frac{d}{d+1} + \varepsilon} + m + n\right)$ edges, where here $\varepsilon$ is an arbitrarily small constant and $C = C(d,k,t,\varepsilon)$. This result is a far-reaching generalization of the classical Szemer\'edi-Trotter incidence theorem. The proof combines tools from several fields: VC-dimension and shatter functions, polynomial partitioning, and Hilbert polynomials. We also present various applications of our theorem. For example, a general point-variety incidence bound in $\mathbb{R}^d$, an improved bound for a $d$-dimensional variant of the Erd\H{o}s unit distances problem, and more.

We survey the variants of Erd\H{o}s' distinct distances problem and the current best bounds for each of those., Comment: Many recent results were added, a few fixes, and two new sections (bipartite problems and connections to Additive Combinatorics)

We study the structure of planar point sets that determine a small number of distinct distances. Specifically, we show that if a set P of n points determines o(n) distinct distances, then no line contains \Omega(n^{7/8}) points of P and no circle contains \Omega(n^{5/6}) points of P. We rely on the bipartite and partial variant of the Elekes-Sharir framework that was presented by Sharir, Sheffer, and Solymosi in \cite{SSS13}. For the case of lines we combine this framework with a theorem from additive combinatorics, and for the case of circles we combine it with some basic algebraic geometry and a recent incidence bound for plane algebraic curves by Wang, Yang, and Zhang \cite{WYZ13}. A significant difference between our approach and that of \cite{SSS13} (and other recent extensions) is that, instead of dealing with distances between two point sets that are restricted to one-dimensional curves, we consider distances between one set that is restricted to a curve and one set with no restrictions on it.

In this note we consider distinct distances determined by points in an integer lattice. We first consider Erdos's lower bound for the square lattice, recast in the setup of the so-called Elekes-Sharir framework \cite{ES11,GK11}, and show that, without a major change, this framework \emph{cannot} lead to Erdos's conjectured lower bound. This shows that the upper bound of Guth and Katz \cite{GK11} for the related 3-dimensional line-intersection problem is tight for this instance. The gap between this bound and the actual bound of Erdos arises from an application of the Cauchy-Schwarz inequality (which is an integral part of the Elekes-Sharir framework). Our analysis relies on two number-theoretic results by Ramanujan. We also consider distinct distances in rectangular lattices of the form $\{(i,j) \mid 0\le i\le n^{1-\alpha},\ 0\le j\le n^{\alpha}\}$, for some $0<\alpha<1/2$, and show that the number of distinct distances in such a lattice is $\Theta(n)$. In a sense, our proof "bypasses" a deep conjecture in number theory, posed by Cilleruelo and Granville \cite{CG07}. A positive resolution of this conjecture would also have implied our bound.

Let P_1 and P_2 be two sets of points in the plane, so that P_1 is contained in a line L_1, P_2 is contained in a line L_2, and L_1 and L_2 are neither parallel nor orthogonal. Then the number of distinct distances determined by the pairs of P_1xP_2 is \Omega(\min{|P_1|^{2/3}|P_2|^{2/3},|P_1|^2, |P_2|^2}). In particular, if |P_1|=|P_2|=m, then the number of these distinct distances is \Omega(m^{4/3}), improving upon the previous bound \Omega(m^{5/4}) of Elekes.

We prove crossing number inequalities for geometric graphs whose vertex sets are taken from a d-dimensional grid of volume N and give applications of these inequalities to counting the number of non-crossing geometric graphs that can be drawn on such grids. In particular, we show that any geometric graph with m >= 8N edges and with vertices on a 3D integer grid of volume N, has \Omega((m^2/n)\log(m/n)) crossings. In d-dimensions, with d >= 4, this bound becomes \Omega(m^2/n). We provide matching upper bounds for all d. Finally, for d >= 4 the upper bound implies that the maximum number of crossing-free geometric graphs with vertices on some d-dimensional grid of volume N is n^\Theta(n). In 3 dimensions it remains open to improve the trivial bounds, namely, the 2^\Omega(n) lower bound and the n^O(n) upper bound., Comment: 16 pages, 3 figures; improved lower-bound in 3-D

We study the maximum numbers of pseudo-triangulations and pointed pseudo-triangulations that can be embedded over a specific set of points in the plane or contained in a specific triangulation. We derive the bounds $O(5.45^N)$ and $\Omega (2.41^N)$ for the maximum number of pointed pseudo-triangulations that can be contained in a specific triangulation over a set of $N$ points. For the number of all pseudo-triangulations contained in a triangulation we derive the bounds $O^*(6.54^N)$ and $\Omega (3.30^N)$. We also prove that $O^*(89.1^N)$ pointed pseudo-triangulations can be embedded over any specific set of $N$ points in the plane, and at most $120^N$ general pseudo-triangulations.

We study cross-graph charging schemes for graphs drawn in the plane. These are charging schemes where charge is moved across vertices of different graphs. Such methods have been recently applied to obtain various properties of triangulations that are embedded over a fixed set of points in the plane. We show how this method can be generalized to obtain results for various other types of graphs that are embedded in the plane. Specifically, we obtain a new bound of $O^*(187.53^N)$ (where the $O^*()$ notation hides polynomial factors) for the maximum number of crossing-free straight-edge graphs that can be embedded over any specific set of $N$ points in the plane (improving upon the previous best upper bound $207.85^N$ in Hoffmann et al.). We also derive upper bounds for numbers of several other types of plane graphs (such as connected and bi-connected plane graphs), and obtain various bounds on expected vertex-degrees in graphs that are uniformly chosen from the set of all crossing-free straight-edge graphs that can be embedded over a specific point set. We then show how to apply the cross-graph charging-scheme method for graphs that allow certain types of crossings. Specifically, we consider graphs with no set of $k$ pairwise-crossing edges (more commonly known as $k$-quasi-planar graphs). For $k=3$ and $k=4$, we prove that, for any set $S$ of $N$ points in the plane, the number of graphs that have a straight-edge $k$-quasi-planar embedding over $S$ is only exponential in $N$.

We establish an improved upper bound for the number of incidences between m points and n circles in three dimensions. The previous best known bound, originally established for the planar case and later extended to any dimension $\ge 2$, is $O*(m^{2/3}n^{2/3} + m^{6/11}n^{9/11}+m+n)$, where the $O*(\cdot)$ notation hides sub-polynomial factors. Since all the points and circles may lie on a common plane (or sphere), it is impossible to improve the bound in R^3 without first improving it in the plane. Nevertheless, we show that if the set of circles is required to be "truly three-dimensional" in the sense that no sphere or plane contains more than $q$ of the circles, for some $q << n$, then the bound can be improved to \[O*(m^{3/7}n^{6/7} + m^{2/3}n^{1/2}q^{1/6} + m^{6/11}n^{15/22}q^{3/22} + m + n). \] For various ranges of parameters (e.g., when $m=\Theta(n)$ and $q = o(n^{7/9})$), this bound is smaller than the lower bound $\Omega*(m^{2/3}n^{2/3}+m+n)$, which holds in two dimensions. We present several extensions and applications of the new bound: (i) For the special case where all the circles have the same radius, we obtain the improved bound $O*(m^{5/11}n^{9/11} + m^{2/3}n^{1/2}q^{1/6} + m + n$. (ii) We present an improved analysis that removes the subpolynomial factors from the bound when $m=O(n^{3/2-\eps})$ for any fixed $\varepsilon >0$. (iii) We use our results to obtain the improved bound $O(m^{15/7})$ for the number of mutually similar triangles determined by any set of $m$ points in R^3. Our result is obtained by applying the polynomial partitioning technique of Guth and Katz using a constant-degree partitioning polynomial (as was also recently used by Solymosi and Tao). We also rely on various additional tools from analytic, algebraic, and combinatorial geometry.

We derive improved upper bounds on the number of crossing-free straight-edge spanning cycles (also known as Hamiltonian tours and simple polygonizations) that can be embedded over any specific set of $N$ points in the plane. More specifically, we bound the ratio between the number of spanning cycles (or perfect matchings) that can be embedded over a point set and the number of triangulations that can be embedded over it. The respective bounds are $O(1.8181^N)$ for cycles and $O(1.1067^N)$ for matchings. These imply a new upper bound of $O(54.543^N)$ on the number of crossing-free straight-edge spanning cycles that can be embedded over any specific set of $N$ points in the plane (improving upon the previous best upper bound $O(68.664^N)$). Our analysis is based on Kasteleyn's linear algebra technique.

We obtain new lower and upper bounds for the maximum multiplicity of some weighted and, respectively, non-weighted common geometric graphs drawn on n points in the plane in general position (with no three points collinear): perfect matchings, spanning trees, spanning cycles (tours), and triangulations. (i) We present a new lower bound construction for the maximum number of triangulations a set of n points in general position can have. In particular, we show that a generalized double chain formed by two almost convex chains admits {\Omega}(8.65^n) different triangulations. This improves the bound {\Omega}(8.48^n) achieved by the double zig-zag chain configuration studied by Aichholzer et al. (ii) We present a new lower bound of {\Omega}(12.00^n) for the number of non-crossing spanning trees of the double chain composed of two convex chains. The previous bound, {\Omega}(10.42^n), stood unchanged for more than 10 years. (iii) Using a recent upper bound of 30^n for the number of triangulations, due to Sharir and Sheffer, we show that n points in the plane in general position admit at most O(68.62^n) non-crossing spanning cycles. (iv) We derive lower bounds for the number of maximum and minimum weighted geometric graphs (matchings, spanning trees, and tours). We show that the number of shortest non-crossing tours can be exponential in n. Likewise, we show that both the number of longest non-crossing tours and the number of longest non-crossing perfect matchings can be exponential in n. Moreover, we show that there are sets of n points in convex position with an exponential number of longest non-crossing spanning trees. For points in convex position we obtain tight bounds for the number of longest and shortest tours. We give a combinatorial characterization of the longest tours, which leads to an O(nlog n) time algorithm for computing them.

We generalize the notions of flippable and simultaneously flippable edges in a triangulation of a set S of points in the plane to so-called \emph{pseudo-simultaneously flippable edges}. Such edges are related to the notion of convex decompositions spanned by S. We prove a worst-case tight lower bound for the number of pseudo-simultaneously flippable edges in a triangulation in terms of the number of vertices. We use this bound for deriving new upper bounds for the maximal number of crossing-free straight-edge graphs that can be embedded on any fixed set of N points in the plane. We obtain new upper bounds for the number of spanning trees and forests as well. Specifically, let tr(N) denote the maximum number of triangulations on a set of N points in the plane. Then we show (using the known bound tr(N) < 30^N) that any N-element point set admits at most 6.9283^N * tr(N) < 207.85^N crossing-free straight-edge graphs, O(4.7022^N) * tr(N) = O(141.07^N) spanning trees, and O(5.3514^N) * tr(N) = O(160.55^N) forests. We also obtain upper bounds for the number of crossing-free straight-edge graphs that have cN, fewer than cN, or more than cN edges, for any constant parameter c, in terms of c and N.

We study the maximal number of triangulations that a planar set of $n$ points can have, and show that it is at most $30^n$. This new bound is achieved by a careful optimization of the charging scheme of Sharir and Welzl (2006), which has led to the previous best upper bound of $43^n$ for the problem. Moreover, this new bound is useful for bounding the number of other types of planar (i.e., crossing-free) straight-line graphs on a given point set. Specifically, we derive new upper bounds for the number of planar graphs ($o(239.4^n)$), spanning cycles ($O(70.21^n)$), and spanning trees ($160^n$).