On numbers of pseudo-triangulations (Q1947983): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: reviewed by (P1447): Item:Q478831 |
||
Property / reviewed by | |||
Property / reviewed by: Juan Monterde / rank | |||
Revision as of 05:20, 15 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On numbers of pseudo-triangulations |
scientific article |
Statements
On numbers of pseudo-triangulations (English)
0 references
29 April 2013
0 references
After having culminated the work of bounding the maximum number of plane graphs on a set of \(N\) points [\textit{M. Sharir} and \textit{A. Sheffer}, Lect. Notes Comput. Sci. 7704, 19--30 (2013; Zbl 1378.68185)] and, in particular, the lower and upper bounds of possible triangulations, the authors study similar problems related with pseudo-triangulations and pointed pseudo-triangulations. Some discrepancies with results existing in previous literature are carefully worked out. Among the main results, the authors show that the statement saying that the number of pointed pseudo-triangulations that can be embedded over a set \(S\) of \(N\) points is always lesser or equal than \(3^N\) times the number of distinct triangulation over \(S\) is not asymptotically tight. The bound can be improved a little bit. Instead of \(3^N\), the new bound is \(2.97^N\). It seems a very small improvement, but it is the first new result after a decade and it has potential to induce further progress.
0 references
pseudo-triangulation
0 references
triangulation
0 references
plane graph
0 references
graph counting
0 references