Drawing 3-Polytopes with Good Vertex Resolution

Schulz, André (2010) Drawing 3-Polytopes with Good Vertex Resolution. In: Graph Drawing 17th International Symposium, GD 2009, September 22-25, 2009 , pp. 33-44(Official URL: http://dx.doi.org/10.1007/978-3-642-11805-0_6).

Full text not available from this repository.


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 in a 2(n − 2) × 1 × 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.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-642-11805-0_6
Classifications: G Algorithms and Complexity > G.070 Area / Edge Length
M Methods > M.400 Force-directed / Energy-based
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1107

Actions (login required)

View Item View Item