Flips in combinatorial pointed pseudo-triangulations with face degree at most four

0478915 - ÚI 2018 SG eng J - Journal Article
Aichholzer, O. - Hackl, T. - Orden, D. - Pilz, A. - Saumell, Maria - Vogtenhuber, B.
Flips in combinatorial pointed pseudo-triangulations with face degree at most four.
International Journal of Computational Geometry & Applications. Roč. 24, č. 3 (2014), s. 197-224. ISSN 0218-1959
Keywords : bounded face degree * combinatorial pseudo-triangulation * graph diameter * ip graph * pointed pseudo-triangulation
Impact factor: 0.082, year: 2013

In this paper we consider the ip operation for combinatorial pointed pseudotriangulations where faces have size 3 or 4, so-called combinatorial 4-PPTs.We show that every combinatorial 4-PPT is stretchable to a geometric pseudo-triangulation, which in general is not the case if faces may have size larger than 4. Moreover, we prove that the ip graph of combinatorial 4-PPTs is connected and has diameter O(n 2 ), even in the case of labeled vertices with fixed outer face. For this case we provide an ω (n log n) lower bound.
Permanent Link: http://hdl.handle.net/11104/0274962