DIKUL - logo
E-viri
Celotno besedilo
Recenzirano
  • <h>Bounded</h>-<h>degree sp...
    van Renssen, André; Wong, Gladys

    Theoretical computer science, 01/2021, Letnik: 854
    Journal Article

    •We show how to construct a 2-spanner among polygonal obstacles.•We show how to construct a 6-spanner among polygonal obstacles of degree at most 15.•We show how to construct a 6-spanner among polygonal obstacles of degree at most 10.•We show how to construct a 6-spanner among polygonal obstacles of degree at most 7. Let V be a finite set of vertices in the plane and S be a finite set of polygonal obstacles, where the vertices of S are in V. We show how to construct a plane 2-spanner of the visibility graph of V with respect to S. As this graph can have unbounded degree, we modify it in three easy-to-follow steps, in order to bound the degree to 7 at the cost of slightly increasing the spanning ratio to 6.