On Bounded-Degree Plane Geometric Spanners

VCLA and WPI will host a talk by Iyad Kanj on February 18, 2015.

ABSTRACT

Let E be the complete Euclidean graph on a finite set of points embedded in the plane. Given a constant t >= 1, a spanning subgraph G of E is a (geometric) t-spanner of E, or simply a spanner of E if, for any two vertices u, v in E, their distance in G is at most t times |uv|. A spanner is plane if its edges do not cross. Without the planarity constraint, it is known that a plane spanner of E of maximum degree 3 can be constructed. The constant 3 is the best-known lower bound on the maximum degree of a plane spanner of E. In this talk we survey some results — in a long sequence of results — on bounded-degree plane spanners of E, leading to the most recent result (2014) proving that a plane spanner of E of maximum degree 4 can be constructed (efficiently). The question of whether there exists a plane spanner of E of maximum degree 3 remains open. With kind support of the Vienna Center for Logic and Algorithms (VCLA) and the Wolfgang Pauli Institute (WPI).