Shortest Path Problems in Polygons and Clique Covers

science. Besides theoretical interests, they are often used as
geometric models. An important and often studied class of problems
related to polygons are shortest path problems, where short means
minimal with respect to a given criterion, e.g. shortest in length or
minimal number of bends (where the bends may or may not be restricted
to appear only at vertices of the polygon). A combinatorial structure
related to some shortest path problems is the visibility graph of a
polygon, where vertices are adjacent if they can see each other inside
the polygon. A compressed representation of this graph, e.g. by a
clique cover, may therefore be desirable.

In the first part of my talk I will give a brief overview on shortest
paths problems in polygons. Then we examine if and how clique
coverings of the visibility graph can be utilized. In the last part I
will present a subquadratic algorithm for finding minimum link paths
without Steiner-points.