×

On numbers of pseudo-triangulations. (English) Zbl 1272.65021

After having culminated the work of bounding the maximum number of plane graphs on a set of \(N\) points [M. Sharir and 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.

MSC:

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

Citations:

Zbl 1378.68185
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aichholzer, O.; Hackl, T.; Huemer, C.; Hurtado, F.; Krasser, H.; Vogtenhuber, B., On the number of plane geometric graphs, Graphs Combin., 23, 1, 67-84 (2007) · Zbl 1119.05056
[3] Aichholzer, O.; Orden, D.; Santos, F.; Speckmann, B., On the number of pseudo-triangulations of certain point sets, J. Combin. Theory Ser. A, 115, 2, 254-278 (2008) · Zbl 1133.68076
[4] Ajtai, M.; Chvátal, V.; Newborn, M.; Szemerédi, E., Crossing-free subgraphs, Ann. Discrete Math., 12, 9-12 (1982) · Zbl 0502.05021
[5] Buchin, K.; Schulz, A., On the number of spanning trees a planar graph can have, (Proc. 18th Annual European Symposium on Algorithms. Proc. 18th Annual European Symposium on Algorithms, Lecture Notes in Comput. Sci., vol. 6346 (2010), Springer-Verlag: Springer-Verlag Berlin), 110-121 · Zbl 1287.05062
[6] Dumitrescu, A.; Schulz, A.; Sheffer, A.; Tóth, Cs. D., Bounds on the maximum multiplicity of some common geometric graphs, in: 28th International Symposium on Theoretical Aspects of Computer Science (STACS), 2011, pp. 637-648, full version in · Zbl 1230.68206
[7] García, A.; Noy, M.; Tejel, J., Lower bounds on the number of crossing-free subgraphs of \(K_N\), Comput. Geom. Theory Appl., 16, 4, 211-221 (2000) · Zbl 0966.68158
[8] Haas, R.; Orden, D.; Rote, G.; Santos, F.; Servatius, B.; Servatius, H.; Souvaine, D.; Streinu, I.; Whiteley, W., Planar minimally rigid graphs and pseudo-triangulations, Comput. Geom. Theory Appl., 31, 1-2, 31-61 (2005) · Zbl 1070.65014
[9] Hall, P., On representatives of subsets, J. Lond. Math. Soc., 10, 1, 26-30 (1935) · JFM 61.0067.01
[10] Hoffmann, M.; Schulz, A.; Sharir, M.; Sheffer, A.; Tóth, Cs. D.; Welzl, E., Counting plane graphs: Flippability and its applications, (Pach, J., Thirty Essays on Geometric Graph Theory (2013), Springer: Springer Berlin), also in · Zbl 1272.05080
[11] Laman, G., On graphs and rigidity of plane skeletal structures, J. Engrg. Math., 4, 4, 331-340 (1970) · Zbl 0213.51903
[13] Rote, G.; Santos, F.; Streinu, I., Pseudo-triangulations — a survey, (Surveys on Discrete and Computational Geometry — Twenty Years Later. Surveys on Discrete and Computational Geometry — Twenty Years Later, Contemp. Math., vol. 453 (2008), American Mathematical Society), 343-410 · Zbl 1169.05027
[14] Rote, G.; Wang, C.; Wang, L.; Xu, Y., On constrained minimum pseudotriangulations, (Proc. 9th Computing and Combinatorics Conf.. Proc. 9th Computing and Combinatorics Conf., Lecture Notes in Comput. Sci., vol. 2697 (2003), Springer-Verlag: Springer-Verlag Berlin), 445-454 · Zbl 1276.68164
[15] Sharir, M.; Sheffer, A., Counting triangulations of planar point sets, Electron. J. Combin., 18, 1, P70 (2011), also in · Zbl 1218.05072
[17] Sharir, M.; Sheffer, A.; Welzl, E., On degrees in random triangulations of point sets, J. Combin. Theory Ser. A, 118, 1979-1999 (2011) · Zbl 1232.05217
[18] Sharir, M.; Sheffer, A.; Welzl, E., Counting plane graphs: Perfect matchings, spanning cycles, and Kasteleynʼs technique, in: Proc. 28th ACM Symp. on Computational Geometry, 2012, pp. 189-198, also in · Zbl 1293.05307
[19] Sharir, M.; Welzl, E., On the number of crossing-free matchings (cycles, and partitions), SIAM J. Comput., 36, 3, 695-720 (2006) · Zbl 1120.68085
[21] Streinu, I., Pseudo-triangulations, rigidity and motion planning, Discrete Comput. Geom., 34, 4, 587-635 (2005) · Zbl 1084.68134
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.