Transforming plane triangulations by simultaneous diagonal flips
| Autor: | Jean-Lou De Carufel, Tanvir Kaykobad |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Diagonal
0102 computer and information sciences 02 engineering and technology 01 natural sciences Graph Computer Science Applications Theoretical Computer Science Planar graph Combinatorics symbols.namesake 010201 computation theory & mathematics Outerplanar graph Signal Processing 0202 electrical engineering electronic engineering information engineering symbols 020201 artificial intelligence & image processing Hamiltonian (quantum mechanics) Information Systems Mathematics |
| Zdroj: | Information Processing Letters. 170:106120 |
| ISSN: | 0020-0190 |
| DOI: | 10.1016/j.ipl.2021.106120 |
| Popis: | We study the number of simultaneous diagonal flips required to transform any triangulation into any other. The best known algorithm requires no more than 4 × ( 2 log 54 53 + 2 log 6 5 ) log n + 2 ≈ 327.1 log n simultaneous flips. This bound is asymptotically tight. In this paper, exploiting some newly discovered properties of blocking and blocked chords we bring the leading constant down to ≈85.8. We also show that 6 log n log 9 7 + 1 ≈ 16.6 log n simultaneous flips are sufficient to transform any maximal outerplane graph into any other. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect