On numbers of pseudo-triangulations (Q1947983): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
Changed an Item |
||
Property / arXiv ID | |||
Property / arXiv ID: 1210.7126 / rank | |||
Normal rank |
Revision as of 00:08, 19 April 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