Improved Spanning Ratio for Low Degree Plane Spanners
We describe an algorithm that builds a plane spanner with a maximum degree of 8 and a spanning ratio of ≈ 4.414 with respect to the complete graph. This is the best currently known spanning ratio for a plane spanner with a maximum degree of less than 14.
|Keywords||Bounded degree, Computational geometry, Degree, Graph theory, Graphs, Plane, Spanners, Spanning graph, Spanning ratio|
Bose, P, Hill, D. (Darryl), & Smid, M. (2018). Improved Spanning Ratio for Low Degree Plane Spanners. Algorithmica, 80(3), 935–976. doi:10.1007/s00453-017-0305-5