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, Chicago, IL, USA , pp. 33-44 (Official URL: http://dx.doi.org/10.1007/978-3-642-11805-0_6).

Full text not available from this repository.

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 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
ID Code:1107

Repository Staff Only: item control page

References

Chrobak, M., Goodrich, M.T., Tamassia, R.: Convex drawings of graphs in two and three dimensions (preliminary version). In: 12th Symposium on Computational Geometry, pp. 319–328 (1996)

Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. J. Symb. Comput. 9(3), 251–280 (1990)

Crapo, H., Whiteley, W.: Plane self stresses and projected polyhedraI: The basic pattern. Structural Topology 20, 55–78 (1993)

Das, G., Goodrich, M.T.: On the complexity of optimization problems for 3-dimensional convex polyhedra and decision trees. Comput. Geom. Theory Appl. 8(3), 123–137 (1997)

de Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica 10(1), 41–51 (1990)

Eades, P., Garvan, P.: Drawing stressed planar graphs in three dimensions. In: Brandenburg, F.J. (ed.) GD 1995. LNCS, vol. 1027, pp. 212–223. Springer, Heidelberg (1996)

Gortler, S.J., Gotsman, C., Thurston, D.: Discrete one-forms on meshes and applications to 3d mesh parameterization. Computer Aided Geometric Design 23(2), 83–112 (2006)

Hopcroft, J.E., Kahn, P.J.: A paradigm for robust geometric algorithms. Algorithmica 7(4), 339–380 (1992)

Lipton, R.J., Rose, D., Tarjan, R.: Generalized nested dissection. SIAM J. Numer. Anal. 16(2), 346–358 (1979)

Lipton, R.J., Tarjan, R.E.: Applications of a planar separator theorem. SIAM J. Comput. 9(3), 615–627 (1980)

Maxwell, J.C.: On reciprocal figures and diagrams of forces. Phil. Mag. Ser. 27, 250–261 (1864)

Ribó Mor, A., Rote, G., Schulz, A.: Small grid embeddings of 3-polytopes (2009)(submitted for publication),http://arxiv.org/abs/0908.0488

Richter-Gebert, J.: Realization Spaces of Polytopes. Lecture Notes in Mathematics, vol. 1643. Springer, Heidelberg (1996)

Schnyder, W.: Embedding planar graphs on the grid. In: Proc. 1st ACM-SIAM Sympos. Discrete Algorithms, pp. 138–148 (1990)

Schramm, O.: Existence and uniqueness of packings with specified combinatorics. Israel J. Math. 73, 321–341 (1991)

Steinitz, E.: Encyclopädie der mathematischen Wissenschaften. In: Polyeder und Raumteilungen, pp. 1–139 (1922)

Tutte, W.T.: How to draw a graph. Proceedings London Mathematical Society 13(52), 743–768 (1963)

Whiteley, W.: Motion and stresses of projected polyhedra. Structural Topology 7, 13–38 (1982)

Whitney, H.: A set of topological invariants for graphs. Amer. J. Math. 55, 235–321 (1933) 20. Zhang, F.: Matrix Theory. Springer, Heidelberg (1999)