**O. Aichholzer and F. Aurenhammer**

A novel type of skeleton for general polygonal figures, the straight skeleton
of a planar straight line graph , is introduced and discussed.
Exact bounds on the size of are derived. The straight line structure
of and its lower combinatorial complexity may make preferable
to the widely used Voronoi diagram (or medial axis) of in several
applications. We explain why has no Voronoi diagram based
interpretation and why standard construction techniques fail to work. A
simple space algorithm for constructing is proposed. The
worst-case running time is , but the algorithm can be expected
to be practically efficient, and it is easy to implement. We also show that
the concept of is flexible enough to allow an individual weighting of
the edges and vertices of , without changes in the maximal size of ,
or in the method of construction. Apart from offering an alternative to
Voronoi-type skeletons, these generalizations of have applications to
the reconstruction of a geographical terrain from a given river map, and to
the construction of a polygonal roof above a given layout of ground walls.