Abstract
We introduce an algorithm that embeds a given 3-connected planar graph as a convex 3-polytope with integer coordinates. The size of the coordinates is bounded by O(27.55n)=O(188n). If the graph contains a triangle we can bound the integer coordinates by O(24.82n). If the graph contains a quadrilateral we can bound the integer coordinates by O(25.46n). The crucial part of the algorithm is to find a convex plane embedding whose edges can be weighted such that the sum of the weighted edges, seen as vectors, cancel at every point. It is well known that this can be guaranteed for the interior vertices by applying a technique of Tutte. We show how to extend Tutte’s ideas to construct a plane embedding where the weighted vector sums cancel also on the vertices of the boundary face.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Acketa, D.M., Žuníć, J.D.: On the maximal number of edges of convex digital polygons included into an m×m-grid. J. Comb. Theory Ser. A 69(2), 358–368 (1995)
Andrews, G.E.: A lower bound for the volume of strictly convex bodies with many boundary lattice points. Trans. Am. Math. Soc. 99, 272–277 (1961)
Bárány, I., Rote, G.: Strictly convex drawings of planar graphs. Doc. Math. 11, 369–391 (2006)
Bonichon, N., Felsner, S., Mosbah, M.: Convex drawings of 3-connected planar graphs. Algorithmica 47, 399–420 (2007)
Buchin, K., Schulz, A.: On the number of spanning trees a planar graph can have. In: Proceedings of the 18th Annual European Symposium on Algorithms, ESA 2010 (2010). dx.doi.org/10.1007/978-3-642-15775-2_10
Chrobak, M., Goodrich, M.T., Tamassia, R.: Convex drawings of graphs in two and three dimensions (preliminary version). In: 12th Annual Symposium on Computational Geometry, pp. 319–328 (1996)
Connelly, R., Demaine, E.D., Rote, G.: Straightening polygonal arcs and convexifying polygonal cycles. Discrete Comput. Geom. 30, 205–239 (2003)
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 polyhedra I: the basic pattern. Struct. Topol. 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.) Graph Drawing. Lecture Notes in Computer Science, vol. 1027, pp. 212–223. Springer, Berlin (1995)
Gortler, S.J., Gotsman, C., Thurston, D.: Discrete one-forms on meshes and applications to 3d mesh parameterization. Comput. Aided Geom. Des. 23(2), 83–112 (2006)
Hopcroft, J.E., Kahn, P.J.: A paradigm for robust geometric algorithms. Algorithmica 7(4), 339–380 (1992)
Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press, Cambridge (1990)
Lewin, M.: A generalization of the matrix-tree theorem. Math. Z. 181(1), 55–70 (1982)
Lipton, R.J., Tarjan, R.E.: Applications of a planar separator theorem. SIAM J. Comput. 9(3), 615–627 (1980)
Lipton, R.J., Rose, D., Tarjan, R.: Generalized nested dissection. SIAM J. Numer. Anal. 16(2), 346–358 (1979)
Maxwell, J.C.: On reciprocal figures and diagrams of forces. Philos. Mag. Ser. 27, 250–261 (1864)
Onn, S., Sturmfels, B.: A quantitative Steinitz’ theorem. In: Beiträge zur Algebra und Geometrie, vol. 35, pp. 125–129 (1994)
Ribó Mor, A.: Realization and counting problems for planar structures: trees and linkages, polytopes and polyominoes. PhD Thesis, Freie Universität Berlin (2006)
Ribó Mor, A., Rote, G., Schulz, A.: Embedding 3-polytopes on a small grid. In: SCG’07: Proceedings of 23rd Annual Symposium on Computational Geometry, New York, NY, USA, pp. 112–118. ACM, New York (2007)
Ribó Mor, A., Rote, G., Yong, X.: Upper bounds for the number of spanning trees of a planar graph (2009, in preparation)
Richter-Gebert, J.: Realization Spaces of Polytopes. Lecture Notes in Mathematics, vol. 1643. Springer, Berlin (1996)
Richter-Gebert, J., Ziegler, G.M.: Realization spaces of 4-polytopes are universal. Bull. Am. Math. Soc. 32, 403 (1995)
Rote, G.: The number of spanning trees in a planar graph. In: Oberwolfach Reports, vol. 2, pp. 969–973. European Mathematical Society, Finland (2005)
Schnyder, W.: Embedding planar graphs on the grid. In: Proceedings of the 1st ACM-SIAM Symposium Discrete Algorithms, pp. 138–148 (1990)
Schramm, O.: Existence and uniqueness of packings with specified combinatorics. Isr. J. Math. 73, 321–341 (1991)
Schulz, A.: Lifting planar graphs to realize integral 3-polytopes and topics in pseudo-triangulations. PhD Thesis, Freie Universität Berlin (2008)
Schulz, A.: Drawing 3-polytopes with good vertex resolution. In: Eppstein, D., Gansner, E.R. (eds.) Graph Drawing. Lecture Notes in Computer Science, vol. 5849, pp. 33–44. Springer, Berlin (2009)
Steinitz, E.: Polyeder und Raumeinteilungen. In: Encyclopädie der mathematischen Wissenschaften. (Geometrie), vol. 3, pp. 1–139. Teubner, Leipzig (1916). Chap. 12
Thiele, T.: Extremalprobleme für Punktmengen. Master’s Thesis, Freie Universität Berlin (1991)
Tutte, W.T.: Convex representations of graphs. Proc. Lond. Math. Soc. 10(38), 304–320 (1960)
Tutte, W.T.: How to draw a graph. Proc. Lond. Math. Soc. 13(52), 743–768 (1963)
Voss, K., Klette, R.: On the maximal number of edges of convex digital polygons included into a square. Počít. Umelá Intel. 1(6), 549–558 (1982) (in Russian)
Whiteley, W.: Motion and stresses of projected polyhedra. Struct. Topol. 7, 13–38 (1982)
Zhang, F.: Matrix Theory. Springer, Berlin (1999)
Zickfeld, F.: Geometric and combinatorial structures on graphs. PhD Thesis, Technical University Berlin (December 2007)
Author information
Authors and Affiliations
Corresponding author
Additional information
Research of A. Ribó Mor was partially supported by the Deutsche Forschungsgemeinschaft within the European Research Training Network Combinatorics, Geometry and Computation (No. GRK 588/2).
Research of A. Schulz was partially supported by the German Research Foundation (DFG) under grant SCHU 2458/1-1.
Rights and permissions
About this article
Cite this article
Ribó Mor, A., Rote, G. & Schulz, A. Small Grid Embeddings of 3-Polytopes. Discrete Comput Geom 45, 65–87 (2011). https://doi.org/10.1007/s00454-010-9301-0
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-010-9301-0