Lower bounds on the number of crossing-free subgraphs of K_N

DOI10.1016/S0925-7721(00)00010-9zbMATH Open0966.68158MaRDI QIDQ1594599FDOQ1594599

Authors: Alfredo García, Marc Noy, Javier Tejel

Publication date: 10 April 2001

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

Recommendations

On the Number of Crossing‐Free Matchings, Cycles, and Partitions
The Number of Crossing Free Configurations on Finite Point Sets in the Plane
An improved lower bound on the maximum number of non-crossing spanning trees
Lower bounds on the maximum number of non-crossing acyclic graphs
A lower bound for the number of polygonizations of \(N\) points in the plane

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

Cited In (49)

A lower bound for the number of polygonizations of \(N\) points in the plane
Title not available (Why is that?)
Convex hulls of random order types
Touching perfect matchings and halving lines
Algorithmic enumeration of surrounding polygons
Configurations of non-crossing rays and related problems
Perfect matchings with crossings
Reconstruction of the path graph
Circumscribing polygons and polygonizations for disjoint line segments
Convex Polygons in Geometric Triangulations
A combinatorial property on angular orders of plane point sets
On \(k\)-gons and \(k\)-holes in point sets
Perfect matchings with crossings
2-opt moves and flips for area-optimal polygonizations
Area-optimal simple polygonalizations: the CG challenge 2019
A new lower bound on the maximum number of plane graphs using production matrices
Point sets with many non-crossing perfect matchings
Non-crossing Hamiltonian paths and cycles in output-polynomial time
Title not available (Why is that?)
Disjoint compatible geometric matchings
Disjoint compatibility graph of non-crossing matchings of points in convex position
Lower bounds on the maximum number of non-crossing acyclic graphs
On numbers of pseudo-triangulations
Crossing-free perfect matchings in wheel point sets
A better upper bound on the number of triangulations of a planar point set
A lower bound on the number of triangulations of planar point sets
Counting triangulations and other crossing-free structures via onion layers
Counting polygon triangulations is hard
Convex polygons in geometric triangulations
On balanced 4-holes in bichromatic point sets
On the number of plane geometric graphs
Automated mathematical discovery and verification: minimizing pentagons in the plane
4-holes in point sets
On the number of pseudo-triangulations of certain point sets
Sequences of spanning trees and a fixed tree theorem
Title not available (Why is that?)
On the diameter of geometric path graphs of points in convex position
Planar tree transformation: results and counterexample
On the number of crossing-free partitions
Transforming spanning trees: A lower bound
A QPTAS for the base of the number of crossing-free structures on a planar point set
Connecting polygonizations via stretches and twangs
On the Number of Crossing‐Free Matchings, Cycles, and Partitions
The Mathematics of Ferran Hurtado: A Brief Survey
Many touchings force many crossings
Many touchings force many crossings
Hamiltonian Alternating Paths on Bicolored Double-Chains
Counting plane graphs: cross-graph charging schemes
Counting triangulations and other crossing-free structures approximately

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1594599)