English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We obtain new lower and upper bounds for the maximum multiplicity of someweighted and, respectively, non-weighted common geometric graphs drawn on npoints 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 oftriangulations a set of n points in general position can have. In particular,we show that a generalized double chain formed by two almost convex chainsadmits {\Omega}(8.65^n) different triangulations. This improves the bound{\Omega}(8.48^n) achieved by the double zig-zag chain configuration studied byAichholzer et al.  (ii) We present a new lower bound of {\Omega}(12.00^n) for the number ofnon-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 generalposition admit at most O(68.62^n) non-crossing spanning cycles.  (iv) We derive lower bounds for the number of maximum and minimum weightedgeometric graphs (matchings, spanning trees, and tours). We show that thenumber of shortest non-crossing tours can be exponential in n. Likewise, weshow that both the number of longest non-crossing tours and the number oflongest non-crossing perfect matchings can be exponential in n. Moreover, weshow that there are sets of n points in convex position with an exponentialnumber of longest non-crossing spanning trees. For points in convex position weobtain tight bounds for the number of longest and shortest tours. We give acombinatorial characterization of the longest tours, which leads to an O(nlogn) time algorithm for computing them.

Bounds on the maximum multiplicity of some common geometric graphs