Movatterモバイル変換

[0]ホーム
URL:

Skip to main content
Springer Nature Link
Log in

Small Grid Embeddings of 3-Polytopes

  • Published:
Discrete & Computational Geometry Aims and scope Submit manuscript

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 byO(27.55n)=O(188n). If the graph contains a triangle we can bound the integer coordinates byO(24.82n). If the graph contains a quadrilateral we can bound the integer coordinates byO(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

ArticleOpen access17 March 2023

Explore related subjects

Discover the latest articles, books and news in related subjects, suggested using machine learning.

References

  1. Acketa, D.M., Žuníć, J.D.: On the maximal number of edges of convex digital polygons included into anm×m-grid. J. Comb. Theory Ser. A69(2), 358–368 (1995)

    Article MATH  Google Scholar 

  2. 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)

    Article MATH  Google Scholar 

  3. Bárány, I., Rote, G.: Strictly convex drawings of planar graphs. Doc. Math.11, 369–391 (2006)

    MATH MathSciNet  Google Scholar 

  4. Bonichon, N., Felsner, S., Mosbah, M.: Convex drawings of 3-connected planar graphs. Algorithmica47, 399–420 (2007)

    Article MATH MathSciNet  Google Scholar 

  5. 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

    Google Scholar 

  6. 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)

    Google Scholar 

  7. Connelly, R., Demaine, E.D., Rote, G.: Straightening polygonal arcs and convexifying polygonal cycles. Discrete Comput. Geom.30, 205–239 (2003)

    MATH MathSciNet  Google Scholar 

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

    Article MATH MathSciNet  Google Scholar 

  9. Crapo, H., Whiteley, W.: Plane self stresses and projected polyhedra I: the basic pattern. Struct. Topol.20, 55–78 (1993)

    MATH MathSciNet  Google Scholar 

  10. 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)

    MATH MathSciNet  Google Scholar 

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

    Article MATH MathSciNet  Google Scholar 

  12. 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)

    Chapter  Google Scholar 

  13. 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)

    Article MATH MathSciNet  Google Scholar 

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

    Article MATH MathSciNet  Google Scholar 

  15. Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press, Cambridge (1990)

    MATH  Google Scholar 

  16. Lewin, M.: A generalization of the matrix-tree theorem. Math. Z.181(1), 55–70 (1982)

    Article MATH MathSciNet  Google Scholar 

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

    Article MATH MathSciNet  Google Scholar 

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

    Article MATH MathSciNet  Google Scholar 

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

    Google Scholar 

  20. Onn, S., Sturmfels, B.: A quantitative Steinitz’ theorem. In: Beiträge zur Algebra und Geometrie, vol. 35, pp. 125–129 (1994)

    Google Scholar 

  21. Ribó Mor, A.: Realization and counting problems for planar structures: trees and linkages, polytopes and polyominoes. PhD Thesis, Freie Universität Berlin (2006)

  22. 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)

    Google Scholar 

  23. Ribó Mor, A., Rote, G., Yong, X.: Upper bounds for the number of spanning trees of a planar graph (2009, in preparation)

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

    Google Scholar 

  25. Richter-Gebert, J., Ziegler, G.M.: Realization spaces of 4-polytopes are universal. Bull. Am. Math. Soc.32, 403 (1995)

    Article MATH MathSciNet  Google Scholar 

  26. Rote, G.: The number of spanning trees in a planar graph. In: Oberwolfach Reports, vol. 2, pp. 969–973. European Mathematical Society, Finland (2005)

    Google Scholar 

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

    Google Scholar 

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

    Article MATH MathSciNet  Google Scholar 

  29. Schulz, A.: Lifting planar graphs to realize integral 3-polytopes and topics in pseudo-triangulations. PhD Thesis, Freie Universität Berlin (2008)

  30. 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)

    Chapter  Google Scholar 

  31. Steinitz, E.: Polyeder und Raumeinteilungen. In: Encyclopädie der mathematischen Wissenschaften. (Geometrie), vol. 3, pp. 1–139. Teubner, Leipzig (1916). Chap. 12

    Google Scholar 

  32. Thiele, T.: Extremalprobleme für Punktmengen. Master’s Thesis, Freie Universität Berlin (1991)

  33. Tutte, W.T.: Convex representations of graphs. Proc. Lond. Math. Soc.10(38), 304–320 (1960)

    Article MATH MathSciNet  Google Scholar 

  34. Tutte, W.T.: How to draw a graph. Proc. Lond. Math. Soc.13(52), 743–768 (1963)

    Article MATH MathSciNet  Google Scholar 

  35. 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)

    Google Scholar 

  36. Whiteley, W.: Motion and stresses of projected polyhedra. Struct. Topol.7, 13–38 (1982)

    MATH MathSciNet  Google Scholar 

  37. Zhang, F.: Matrix Theory. Springer, Berlin (1999)

    MATH  Google Scholar 

  38. Zickfeld, F.: Geometric and combinatorial structures on graphs. PhD Thesis, Technical University Berlin (December 2007)

Download references

Author information

Authors and Affiliations

  1. Gesellschaft zur Förderung angewandter Informatik e.V., Berlin, Germany

    Ares Ribó Mor

  2. Institut für Informatik, Freie Universität Berlin, Berlin, Germany

    Günter Rote

  3. Institut für Mathematische Logik und Grundlagenforschung, Universität Münster, Münster, Germany

    André Schulz

Authors
  1. Ares Ribó Mor
  2. Günter Rote
  3. André Schulz

Corresponding author

Correspondence toAndré Schulz.

Additional information

Research of A. Ribó Mor was partially supported by the Deutsche Forschungsgemeinschaft within the European Research Training NetworkCombinatorics, 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 Geom45, 65–87 (2011). https://doi.org/10.1007/s00454-010-9301-0

Download citation

Keywords

Advertisement

[8]ページ先頭
©2009-2026 Movatter.jp