Empty Triangles in Complete Topological Graphs
Ruiz-Vargas, Andres
In: Discrete & Computational Geometry, 2015, vol. 53, no. 4, p. 703-712
Aggiungi alla tua lista- Summary
- A simple topological graph is a graph drawn in the plane so that its edges are represented by continuous arcs with the property that any two of them meet at most once. Let $$G$$ G be a complete simple topological graph on $$n$$ n vertices. The three edges induced by any triplet of vertices in $$G$$ G form a simple closed curve. If this curve contains no vertex in its interior (exterior), then we say that the triplet forms an empty triangle. In 1998, Harborth proved that $$G$$ G has at least 2 empty triangles, and he conjectured that the number of empty triangles is at least $$2n/3$$ 2 n / 3 . We settle Harborth's conjecture in the affirmative.