Linear axis for planar straight line graphs
Kira Vyatkina · 2009
A linear axis is a straight line skeleton for a polygonal shape. The concept of a linear axis ε-equivalent to the medial axis has been introduced and studied for simple polygons and for those with holes. In this paper, we generalize the notions of a linear axis and of ε-equivalence to the case of planar straight line graphs. We show that for some graphs, a linear axis ε-equivalent to the medial axis does not exist, for any ε> 0. However, if the graph vertices are in general position, a sought linear axis does exist for any ε> 0, and can be computed in O(n log n) time in the absence of certain correlations in the graph structure.