{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,22]],"date-time":"2025-12-22T04:41:42Z","timestamp":1766378502430,"version":"3.38.0"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2010,9,30]],"date-time":"2010-09-30T00:00:00Z","timestamp":1285804800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2011,1]]},"DOI":"10.1007\/s00454-010-9301-0","type":"journal-article","created":{"date-parts":[[2010,9,29]],"date-time":"2010-09-29T18:34:19Z","timestamp":1285785259000},"page":"65-87","source":"Crossref","is-referenced-by-count":13,"title":["Small Grid Embeddings of 3-Polytopes"],"prefix":"10.1007","volume":"45","author":[{"given":"Ares","family":"Rib\u00f3\u00a0Mor","sequence":"first","affiliation":[]},{"given":"G\u00fcnter","family":"Rote","sequence":"additional","affiliation":[]},{"given":"Andr\u00e9","family":"Schulz","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2010,9,30]]},"reference":[{"issue":"2","key":"9301_CR1","doi-asserted-by":"crossref","first-page":"358","DOI":"10.1016\/0097-3165(95)90058-6","volume":"69","author":"D.M. Acketa","year":"1995","unstructured":"Acketa, D.M., \u017dun\u00ed\u0107, J.D.: On the maximal number of edges of convex digital polygons included into an m\u00d7m-grid. J. Comb. Theory Ser. A 69(2), 358\u2013368 (1995)","journal-title":"J. Comb. Theory Ser. A"},{"key":"9301_CR2","doi-asserted-by":"crossref","first-page":"272","DOI":"10.1090\/S0002-9947-1961-0120222-7","volume":"99","author":"G.E. Andrews","year":"1961","unstructured":"Andrews, G.E.: A lower bound for the volume of strictly convex bodies with many boundary lattice points. Trans. Am. Math. Soc. 99, 272\u2013277 (1961)","journal-title":"Trans. Am. Math. Soc."},{"key":"9301_CR3","doi-asserted-by":"crossref","first-page":"369","DOI":"10.4171\/dm\/214","volume":"11","author":"I. B\u00e1r\u00e1ny","year":"2006","unstructured":"B\u00e1r\u00e1ny, I., Rote, G.: Strictly convex drawings of planar graphs. Doc. Math. 11, 369\u2013391 (2006)","journal-title":"Doc. Math."},{"key":"9301_CR4","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1007\/s00453-006-0177-6","volume":"47","author":"N. Bonichon","year":"2007","unstructured":"Bonichon, N., Felsner, S., Mosbah, M.: Convex drawings of 3-connected planar graphs. Algorithmica 47, 399\u2013420 (2007)","journal-title":"Algorithmica"},{"key":"9301_CR5","volume-title":"Proceedings of the 18th Annual European Symposium on Algorithms, ESA 2010","author":"K. Buchin","year":"2010","unstructured":"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"},{"key":"9301_CR6","first-page":"319","volume-title":"12th Annual Symposium on Computational Geometry","author":"M. Chrobak","year":"1996","unstructured":"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\u2013328 (1996)"},{"key":"9301_CR7","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1007\/s00454-003-0006-7","volume":"30","author":"R. Connelly","year":"2003","unstructured":"Connelly, R., Demaine, E.D., Rote, G.: Straightening polygonal arcs and convexifying polygonal cycles. Discrete Comput. Geom. 30, 205\u2013239 (2003)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"9301_CR8","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","volume":"9","author":"D. Coppersmith","year":"1990","unstructured":"Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. J. Symb. Comput. 9(3), 251\u2013280 (1990)","journal-title":"J. Symb. Comput."},{"key":"9301_CR9","first-page":"55","volume":"20","author":"H. Crapo","year":"1993","unstructured":"Crapo, H., Whiteley, W.: Plane self stresses and projected polyhedra I: the basic pattern. Struct. Topol. 20, 55\u201378 (1993)","journal-title":"Struct. Topol."},{"issue":"3","key":"9301_CR10","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/S0925-7721(97)00006-0","volume":"8","author":"G. Das","year":"1997","unstructured":"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\u2013137 (1997)","journal-title":"Comput. Geom. Theory Appl."},{"issue":"1","key":"9301_CR11","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/BF02122694","volume":"10","author":"H. Fraysseix de","year":"1990","unstructured":"de Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica 10(1), 41\u201351 (1990)","journal-title":"Combinatorica"},{"key":"9301_CR12","series-title":"Lecture Notes in Computer Science","first-page":"212","volume-title":"Graph Drawing","author":"P. Eades","year":"1995","unstructured":"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\u2013223. Springer, Berlin (1995)"},{"issue":"2","key":"9301_CR13","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/j.cagd.2005.05.002","volume":"23","author":"S.J. Gortler","year":"2006","unstructured":"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\u2013112 (2006)","journal-title":"Comput. Aided Geom. Des."},{"issue":"4","key":"9301_CR14","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1007\/BF01758769","volume":"7","author":"J.E. Hopcroft","year":"1992","unstructured":"Hopcroft, J.E., Kahn, P.J.: A paradigm for robust geometric algorithms. Algorithmica 7(4), 339\u2013380 (1992)","journal-title":"Algorithmica"},{"key":"9301_CR15","volume-title":"Matrix Analysis","author":"R.A. Horn","year":"1990","unstructured":"Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press, Cambridge (1990)"},{"issue":"1","key":"9301_CR16","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/BF01214981","volume":"181","author":"M. Lewin","year":"1982","unstructured":"Lewin, M.: A generalization of the matrix-tree theorem. Math. Z. 181(1), 55\u201370 (1982)","journal-title":"Math. Z."},{"issue":"3","key":"9301_CR17","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"R.J. Lipton","year":"1980","unstructured":"Lipton, R.J., Tarjan, R.E.: Applications of a planar separator theorem. SIAM J. Comput. 9(3), 615\u2013627 (1980)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9301_CR18","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1137\/0716027","volume":"16","author":"R.J. Lipton","year":"1979","unstructured":"Lipton, R.J., Rose, D., Tarjan, R.: Generalized nested dissection. SIAM J. Numer. Anal. 16(2), 346\u2013358 (1979)","journal-title":"SIAM J. Numer. Anal."},{"key":"9301_CR19","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1080\/14786446408643663","volume":"27","author":"J.C. Maxwell","year":"1864","unstructured":"Maxwell, J.C.: On reciprocal figures and diagrams of forces. Philos. Mag. Ser. 27, 250\u2013261 (1864)","journal-title":"Philos. Mag. Ser."},{"key":"9301_CR20","first-page":"125","volume-title":"Beitr\u00e4ge zur Algebra und Geometrie","author":"S. Onn","year":"1994","unstructured":"Onn, S., Sturmfels, B.: A quantitative Steinitz\u2019 theorem. In: Beitr\u00e4ge zur Algebra und Geometrie, vol. 35, pp. 125\u2013129 (1994)"},{"key":"9301_CR21","unstructured":"Rib\u00f3 Mor, A.: Realization and counting problems for planar structures: trees and linkages, polytopes and polyominoes. PhD Thesis, Freie Universit\u00e4t Berlin (2006)"},{"key":"9301_CR22","first-page":"112","volume-title":"SCG\u201907: Proceedings of 23rd Annual Symposium on Computational Geometry","author":"A. Rib\u00f3 Mor","year":"2007","unstructured":"Rib\u00f3 Mor, A., Rote, G., Schulz, A.: Embedding 3-polytopes on a small grid. In: SCG\u201907: Proceedings of 23rd Annual Symposium on Computational Geometry, New York, NY, USA, pp. 112\u2013118. ACM, New York (2007)"},{"key":"9301_CR23","unstructured":"Rib\u00f3 Mor, A., Rote, G., Yong, X.: Upper bounds for the number of spanning trees of a planar graph (2009, in preparation)"},{"key":"9301_CR24","series-title":"Lecture Notes in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0093761","volume-title":"Realization Spaces of Polytopes","author":"J. Richter-Gebert","year":"1996","unstructured":"Richter-Gebert, J.: Realization Spaces of Polytopes. Lecture Notes in Mathematics, vol.\u00a01643. Springer, Berlin (1996)"},{"key":"9301_CR25","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1090\/S0273-0979-1995-00604-X","volume":"32","author":"J. Richter-Gebert","year":"1995","unstructured":"Richter-Gebert, J., Ziegler, G.M.: Realization spaces of 4-polytopes are universal. Bull. Am. Math. Soc. 32, 403 (1995)","journal-title":"Bull. Am. Math. Soc."},{"key":"9301_CR26","first-page":"969","volume-title":"Oberwolfach Reports","author":"G. Rote","year":"2005","unstructured":"Rote, G.: The number of spanning trees in a planar graph. In: Oberwolfach Reports, vol. 2, pp. 969\u2013973. European Mathematical Society, Finland (2005)"},{"key":"9301_CR27","first-page":"138","volume-title":"Proceedings of the 1st ACM-SIAM Symposium Discrete Algorithms","author":"W. Schnyder","year":"1990","unstructured":"Schnyder, W.: Embedding planar graphs on the grid. In: Proceedings of the 1st ACM-SIAM Symposium Discrete Algorithms, pp. 138\u2013148 (1990)"},{"key":"9301_CR28","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1007\/BF02773845","volume":"73","author":"O. Schramm","year":"1991","unstructured":"Schramm, O.: Existence and uniqueness of packings with specified combinatorics. Isr. J. Math. 73, 321\u2013341 (1991)","journal-title":"Isr. J. Math."},{"key":"9301_CR29","unstructured":"Schulz, A.: Lifting planar graphs to realize integral 3-polytopes and topics in pseudo-triangulations. PhD Thesis, Freie Universit\u00e4t Berlin (2008)"},{"key":"9301_CR30","series-title":"Lecture Notes in Computer Science","first-page":"33","volume-title":"Graph Drawing","author":"A. Schulz","year":"2009","unstructured":"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\u201344. Springer, Berlin (2009)"},{"key":"9301_CR31","series-title":"(Geometrie)","first-page":"1","volume-title":"Encyclop\u00e4die der mathematischen Wissenschaften","author":"E. Steinitz","year":"1916","unstructured":"Steinitz, E.: Polyeder und Raumeinteilungen. In: Encyclop\u00e4die der mathematischen Wissenschaften. (Geometrie), vol. 3, pp. 1\u2013139. Teubner, Leipzig (1916). Chap. 12"},{"key":"9301_CR32","unstructured":"Thiele, T.: Extremalprobleme f\u00fcr Punktmengen. Master\u2019s Thesis, Freie Universit\u00e4t Berlin (1991)"},{"issue":"38","key":"9301_CR33","doi-asserted-by":"crossref","first-page":"304","DOI":"10.1112\/plms\/s3-10.1.304","volume":"10","author":"W.T. Tutte","year":"1960","unstructured":"Tutte, W.T.: Convex representations of graphs. Proc. Lond. Math. Soc. 10(38), 304\u2013320 (1960)","journal-title":"Proc. Lond. Math. Soc."},{"issue":"52","key":"9301_CR34","doi-asserted-by":"crossref","first-page":"743","DOI":"10.1112\/plms\/s3-13.1.743","volume":"13","author":"W.T. Tutte","year":"1963","unstructured":"Tutte, W.T.: How to draw a graph. Proc. Lond. Math. Soc. 13(52), 743\u2013768 (1963)","journal-title":"Proc. Lond. Math. Soc."},{"issue":"6","key":"9301_CR35","first-page":"549","volume":"1","author":"K. Voss","year":"1982","unstructured":"Voss, K., Klette, R.: On the maximal number of edges of convex digital polygons included into a square. Po\u010d\u00edt. Umel\u00e1 Intel. 1(6), 549\u2013558 (1982) (in Russian)","journal-title":"Po\u010d\u00edt. Umel\u00e1 Intel."},{"key":"9301_CR36","first-page":"13","volume":"7","author":"W. Whiteley","year":"1982","unstructured":"Whiteley, W.: Motion and stresses of projected polyhedra. Struct. Topol. 7, 13\u201338 (1982)","journal-title":"Struct. Topol."},{"key":"9301_CR37","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-5797-2","volume-title":"Matrix Theory","author":"F. Zhang","year":"1999","unstructured":"Zhang, F.: Matrix Theory. Springer, Berlin (1999)"},{"key":"9301_CR38","unstructured":"Zickfeld, F.: Geometric and combinatorial structures on graphs. PhD Thesis, Technical University Berlin (December 2007)"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-010-9301-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-010-9301-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-010-9301-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,26]],"date-time":"2025-02-26T03:59:35Z","timestamp":1740542375000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-010-9301-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,9,30]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["9301"],"URL":"https:\/\/doi.org\/10.1007\/s00454-010-9301-0","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2010,9,30]]}}}