On numbers of pseudo-triangulations

DOI10.1016/J.COMGEO.2012.11.002MaRDI QIDQ1947983zbMATH OpenOpenAlexFDO

Authors Moria Ben-Ner, André Schulz, Adam Sheffer

Publication date 29 April 2013

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1210.7126

zbMATH Keywords

triangulationplane graphgraph countingpseudo-triangulation

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Abstract: 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^{\ast }(6.54^N)$ and $Omega(3.30^N)$. We also prove that $O^{\ast }(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.

Recommendations

• On the number of pseudo-triangulations of certain point sets
• Enumerating pseudo-triangulations in the plane
• Tight degree bounds for pseudo-triangulations of points
• Counting and Enumerating Pointed Pseudotriangulations with the Greedy Flip Algorithm
• Empty pseudo-triangles in point sets

Cites work

• scientific article; zbMATH DE number 5506218 (Why is no real title available?)
• Acute triangulations of polygons
• Bounds on the maximum multiplicity of some common geometric graphs
• Counting Plane Graphs: Cross-Graph Charging Schemes
• Counting plane graphs: perfect matchings, spanning cycles, and Kasteleyn's technique
• Counting triangulations of planar point sets
• Crossing-Free Subgraphs
• Gray code enumeration of plane straight-line graphs
• Lower bounds on the number of crossing-free subgraphs of \(K_N\)
• On constrained minimum pseudotriangulations
• On degrees in random triangulations of point sets
• On graphs and rigidity of plane skeletal structures
• On the Number of Crossing‐Free Matchings, Cycles, and Partitions
• On the number of plane geometric graphs
• On the number of pseudo-triangulations of certain point sets
• On the number of spanning trees a planar graph can have
• Planar minimally rigid graphs and pseudo-triangulations
• Pseudo-triangulations -- a survey

Cited in

(10)

• Counting and Enumerating Pointed Pseudotriangulations with the Greedy Flip Algorithm
• On the Delone triangulation numbers
• On the number of triangles in simple arrangements of pseudolines in the real projective plane
• Asymptotic number of triangulations with vertices in \(\mathbb{Z}^2\)
• The number of geometric bistellar neighbors of a triangulation
• Empty pseudo-triangles in point sets
• Enumerating pseudo-triangulations in the plane
• On the number of pseudo-triangulations of certain point sets
• Pseudo-triangulations -- a survey
• Computing pseudotriangulations via branched coverings

This page was built for publication: On numbers of pseudo-triangulations

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