|
| | | |
Linear Axis for Planar Straight Line Graphs
Vyatkina, K.
A linear axis is a straight line skeleton for a polygonal shape. The concept of a linear axis \epsilon-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 \epsilon-equivalence to the case of planar straight line
graphs. We show that for some graphs, a linear axis
\epsilon-equivalent to the medial axis does not exist, for any
\epsilon > 0. However, if the graph vertices are in general
position, a sought linear axis does exist for any \epsilon > 0,
and can be computed in O(n log n) time in the absence of certain correlations in the graph structure. |
Cite as: Vyatkina, K. (2009). Linear Axis for Planar Straight Line Graphs. In Proc. Fifteenth Computing: The Australasian Theory Symposium (CATS 2009), Wellington, New Zealand. CRPIT, 94. Downey, R. and Manyem, P., Eds. ACS. 137-150. |
(from crpit.com)
(local if available)
|
|