Embedding 3-polytopes on a small grid

ABSTRACT

We show how to embed a 3-connected planar graph with n verticesas a 3-polytope with small integer coordinates.The coordinates are bounded by O(2^7.55n). The crucial part is the construction of a plane embeddingwhich supports an equilibrium stress.We have to guarantee that the size of the coordinates and thestresses are small.This is achieved by applying Tutte's spring embedding method carefully.

REFERENCES

• 1: D.M. Acketa and J.D. Žuníc. On the maximal number of edges of convex digital polygons included into a square grid. Počítače a Umelá Inteligencia, 1(6):549--548, 1982.
• 2: Dragan M. Acketa , Joviša D. Žunic, On the maximal number of edges of convex digital polygons included into an m × m-grid, Journal of Combinatorial Theory Series A, v.69 n.2, p.358-368, Feb. 1995 [doi>10.1016/0097-3165(95)90058-6]
• 3: I. Bárány and G. Rote. Strictly convex drawings of planar graphs. Documenta Math., 11:369--391, 2006.
• 4: N. Bonichon, S. Felsner, and M. Mosbah. Convex drawings of 3--connected planar graphs. Algorithmica, 2006. To appear.
• 5: R. Connelly, E.D. Demaine, and G. Rote. Straightening polygonal arcs and convexifying polygonal cycles. Discrete and Computational Geometry, 30:205--239, 2003.
• 6: H. de Fraysseix, J. Pach, and R. Pollack. How to draw a planar graph on a grid. Combinatorica, 10(1):41--51, 1990.
• 7: J.E. Hopcroft and P.J. Kahn. A paradigm for robust geometric algorithms. Algorithmica, 7(4):339--380, 1992.
• 8: J.C. Maxwell. On reciprocal figures and diagrams of forces. Phil. Mag. Ser., 27:250--261, 1864.
• 9: A. Ribó Mor. Realization and Counting Problems for Planar Structures: Trees and Linkages, Polytopes and Polyominoes. PhD thesis, Freie Universität Berlin, 2006.
• 10: G. Rote. The number of spanning trees in a planar graph. In: Oberwolfach Reports, vol2, European Mathematical Society -- Publishing House, 2005, pp. 969--973.
• 11: J. Richter-Gebert. Realization Spaces of Polytopes, volume 1643 of Lecture Notes in Mathematics. Springer, 1996.
• 12: J. Richter-Gebert and G.M. Ziegler. Realization spaces of 4-polytopes are universal. Bull. Amer. Math. Soc., 32:403, 1995.
• 13: Walter Schnyder, Embedding planar graphs on the grid, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.138-148, January 22-24, 1990, San Francisco, California, United States
• 14: E. Steinitz. Encyclopädie der mathematischen Wissenschaften. In Polyeder und Raumteilungen, pages 1--139. 1922.
• 15: T. Thiele. Extremalprobleme für Punktmengen. Master's thesis, Freie Universität Berlin, 1991.
• 16: W.T. Tutte. Convex representations of graphs. Proceedings London Mathematical Society, 10(38):304--320, 1960.
• 17: W.T. Tutte. How to draw a graph. Proceedings London Mathematical Society, 13(52):743--768, 1963.
• 18: W. Whiteley. Motion and stresses of projected polyhedra. Structural Topology, 7:13--38, 1982.
• 19: F. Zickfeld and G. Ziegler. Personal communication.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Theory

Keywords:
equilibrium stress, spring embedding