Lower bounds on the number of crossing-free subgraphs of \(K_N\)

DOI10.1016/S0925-7721(00)00010-9zbMath0966.68158MaRDI QIDQ1594599

Alfredo Daniel Garcia, Marc Noy, F. Javier Tejel

Publication date: 10 April 2001

Published in: Computational Geometry (Search for Journal in Brave)

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (44)

A better upper bound on the number of triangulations of a planar point set ⋮ Reconstruction of the path graph ⋮ Configurations of non-crossing rays and related problems ⋮ A lower bound on the number of triangulations of planar point sets ⋮ On the number of plane geometric graphs ⋮ Convex Polygons in Geometric Triangulations ⋮ Convex Polygons in Geometric Triangulations ⋮ On the number of crossing-free partitions ⋮ Perfect matchings with crossings ⋮ Circumscribing polygons and polygonizations for disjoint line segments ⋮ 2-Opt Moves and Flips for Area-optimal Polygonizations ⋮ Area-Optimal Simple Polygonalizations: The CG Challenge 2019 ⋮ The Mathematics of Ferran Hurtado: A Brief Survey ⋮ On \(k\)-gons and \(k\)-holes in point sets ⋮ Disjoint compatible geometric matchings ⋮ A QPTAS for the base of the number of crossing-free structures on a planar point set ⋮ Point sets with many non-crossing perfect matchings ⋮ A combinatorial property on angular orders of plane point sets ⋮ Crossing-Free Perfect Matchings in Wheel Point Sets ⋮ On numbers of pseudo-triangulations ⋮ Connecting polygonizations via stretches and twangs ⋮ Counting Plane Graphs: Cross-Graph Charging Schemes ⋮ Many Touchings Force Many Crossings ⋮ 4-holes in point sets ⋮ Counting polygon triangulations is hard ⋮ Touching perfect matchings and halving lines ⋮ On balanced 4-holes in bichromatic point sets ⋮ Algorithmic enumeration of surrounding polygons ⋮ On the number of pseudo-triangulations of certain point sets ⋮ Disjoint compatibility graph of non-crossing matchings of points in convex position ⋮ Planar tree transformation: results and counterexample ⋮ On the diameter of geometric path graphs of points in convex position ⋮ Perfect matchings with crossings ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Monotone paths in geometric triangulations ⋮ Sequences of spanning trees and a fixed tree theorem ⋮ Hamiltonian Alternating Paths on Bicolored Double-Chains ⋮ Many touchings force many crossings ⋮ Transforming spanning trees: A lower bound ⋮ A new lower bound on the maximum number of plane graphs using production matrices ⋮ Counting triangulations and other crossing-free structures approximately ⋮ Lower bounds on the maximum number of non-crossing acyclic graphs ⋮ Counting triangulations and other crossing-free structures via onion layers

This page was built for publication: Lower bounds on the number of crossing-free subgraphs of \(K_N\)