Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
DOI: 10.7155/jgaa.00216 Drawing 3-Polytopes with Good Vertex Resolution AndrĂ© Schulz Vol. 15, no. 1, pp. 33-52, 2011. Regular paper Abstract We study the problem how to obtain a small drawing of a 3-polytope with Euclidean distance between any two points at least 1. The problem can be reduced to a one-dimensional problem, since it is sufficient to guarantee distinct integer x-coordinates. We develop an algorithm that yields an embedding with the desired property such that the polytope is contained inside a 2(n−2)×2 ×1 box. The constructed embedding can be scaled to a grid embedding whose x-coordinates are contained in [0,2(n−2)]. Furthermore, the point set of the embedding has a small spread, which differs from the best possible spread only by a multiplicative constant.
|
Published: February 2011. Revised: October 2010. Reviewed: September 2010. Final: November 2010. Accepted: November 2010. Submitted: December 2009. Communicated by David Eppstein and Emden Gansner |
Journal of Graph Algorithms and Applications |