Realizing Planar Graphs as Convex Polytopes

Rote, Günter (2012) Realizing Planar Graphs as Convex Polytopes. In: Graph Drawing 19th International Symposium, GD 2011, September 21-23, 2011, Eindhoven, The Netherlands , pp. 238-241 (Official URL: http://dx.doi.org/10.1007/978-3-642-25878-7_23).

Full text not available from this repository.

Abstract

This is a survey on methods to construct a three-dimensional convex polytope with a given combinatorial structure, that is, with the edges forming a given 3-connected planar graph, focusing on efforts to achieve small integer coordinates.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-25878-7_23
Classifications:Z Theory > Z.500 Representations
ID Code:1257

Repository Staff Only: item control page

References

Acketa, D.M., Žunić, 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. Amer. Math. Soc. 99, 272–277 (1961)

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

Buchin, K., Schulz, A.: On the Number of Spanning Trees a Planar Graph can have. In: de Berg, M., Meyer, U. (eds.) ESA 2010. LNCS, vol. 6346, pp. 110–121. Springer, Heidelberg (2010)

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)

Demaine, E.D., Schulz, A.: Embedding stacked polytopes on a polynomial-size grid. In: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), San Francisco, pp. 1177–1187 (2011)

Lovász L.: Steinitz representations of polyhedra and the Colin de Verdière number. J. Comb. Theory, Ser. B 82, 223–236 (2000)

Maxwell, J.C.: On reciprocal figures and diagrams of forces. Phil. 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., Rote, G., Schulz, A.: Small grid embeddings of 3-polytopes. Discrete and Computational Geometry 45, 65–87 (2011),http://page.mi.fuberlin.de/rote/Papers/pdf/Small+grid+embeddings+of+3-polytopes.pdf

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

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

Steinitz, E.: Polyeder und Raumeinteilungen. In: Encyclopädie der mathematischen Wissenschaften, vol. III.1.2 (Geometrie), chap. IIIAB12, pp. 1–139. B. G. Teubner, Leipzig (1922)

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

Tutte, W.T.: Convex representations of graphs. Proceedings London Mathematical Society 10(38), 304–320 (1960)

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

Voss, K., Klette, R.: On the maximal number of edges of convex digital polygons included into a square. Počítače a umelá inteligencia 1(6), 549–558 (1982) (in Russian)

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

Zickfeld, F.: Geometric and Combinatorial Structures on Graphs. Ph.D. thesis, Technical University Berlin (December 2007)