{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T17:46:32Z","timestamp":1787507192138,"version":"build-2736575974"},"reference-count":26,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2013,7,25]],"date-time":"2013-07-25T00:00:00Z","timestamp":1374710400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2013,11]]},"abstract":"<jats:p>\n                    We study cross-graph charging schemes for graphs drawn in the plane. These are charging schemes where charge is moved across vertices of different graphs. Such methods have recently been used to obtain various properties of triangulations that are embedded in a fixed set of points in the plane. We generalize this method to obtain results for various other types of graphs that are embedded in the plane. Specifically, we obtain a new bound of\n                    <jats:italic>O<\/jats:italic>\n                    *(187.53\n                    <jats:sup>\n                      <jats:italic>N<\/jats:italic>\n                    <\/jats:sup>\n                    ) (where the\n                    <jats:italic>O<\/jats:italic>\n                    *(\u22c5) notation hides polynomial factors) for the maximum number of crossing-free straight-edge graphs that can be embedded in any specific set of\n                    <jats:italic>N<\/jats:italic>\n                    points in the plane (improving upon the previous best upper bound 207.85\n                    <jats:sup>\n                      <jats:italic>N<\/jats:italic>\n                    <\/jats:sup>\n                    in Hoffmann, Schulz, Sharir, Sheffer, T\u00f3th and Welzl [14]). We also derive upper bounds for numbers of several other types of plane graphs (such as connected and bi-connected plane graphs), and obtain various bounds on the expected vertex-degrees in graphs that are uniformly chosen from the set of all crossing-free straight-edge graphs that can be embedded in a specific point set.\n                  <\/jats:p>\n                  <jats:p>\n                    We then apply the cross-graph charging-scheme method to graphs that allow certain types of crossings. Specifically, we consider graphs with no set of\n                    <jats:italic>k<\/jats:italic>\n                    pairwise crossing edges (more commonly known as\n                    <jats:italic>k<\/jats:italic>\n                    -quasi-planar graphs). For\n                    <jats:italic>k<\/jats:italic>\n                    =3 and\n                    <jats:italic>k<\/jats:italic>\n                    =4, we prove that, for any set\n                    <jats:italic>S<\/jats:italic>\n                    of\n                    <jats:italic>N<\/jats:italic>\n                    points in the plane, the number of graphs that have a straight-edge\n                    <jats:italic>k<\/jats:italic>\n                    -quasi-planar embedding over\n                    <jats:italic>S<\/jats:italic>\n                    is only exponential in\n                    <jats:italic>N<\/jats:italic>\n                    .\n                  <\/jats:p>","DOI":"10.1017\/s096354831300031x","type":"journal-article","created":{"date-parts":[[2013,7,25]],"date-time":"2013-07-25T13:44:13Z","timestamp":1374759853000},"page":"935-954","source":"Crossref","is-referenced-by-count":12,"title":["Counting Plane Graphs: Cross-Graph Charging Schemes"],"prefix":"10.1017","volume":"22","author":[{"given":"MICHA","family":"SHARIR","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"ADAM","family":"SHEFFER","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2013,7,25]]},"reference":[{"key":"S096354831300031X_ref25","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2011.04.002"},{"key":"S096354831300031X_ref20","unstructured":"Rib\u00f3 Mor, A. (2005) Realizations and counting problems for planar structures: Trees and linkages, polytopes and polyominos. PhD thesis, Freie Universit\u00e4t Berlin."},{"key":"S096354831300031X_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(00)00010-9"},{"key":"S096354831300031X_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-009-9143-9"},{"key":"S096354831300031X_ref18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-19391-0_3"},{"key":"S096354831300031X_ref7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-73545-8_12"},{"key":"S096354831300031X_ref22","doi-asserted-by":"publisher","DOI":"10.1016\/S0097-3165(03)00002-5"},{"key":"S096354831300031X_ref19","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2008.06.039"},{"key":"S096354831300031X_ref4","first-page":"9","article-title":"Crossing-free subgraphs.","volume":"12","author":"Ajtai","year":"1982","journal-title":"Ann. Discrete Math."},{"key":"S096354831300031X_ref8","first-page":"39","volume-title":"Proc. 9th Canadian Conference on Computational Geometry","author":"Denny","year":"1997"},{"key":"S096354831300031X_ref23","doi-asserted-by":"crossref","first-page":"#P70","DOI":"10.37236\/557","article-title":"Counting triangulations of planar point sets","volume":"18","author":"Sharir","year":"2011","journal-title":"Electron. J. Combin."},{"key":"S096354831300031X_ref15","first-page":"505","article-title":"Extrait d'une lettre de M. Lam\u00e9 \u00e0 M. Liouville sur cette question: Un polygone convexe \u00e9tant donn\u00e9, de combien de mani\u00e8res peut-on le partager en triangles au moyen de diagonales?","volume":"3","author":"Lam\u00e9","year":"1838","journal-title":"Journal de Math\u00e9matiques Pures et Appliqu\u00e9es"},{"key":"S096354831300031X_ref9","unstructured":"Dumitrescu A. , Schulz A. , Sheffer A. and T\u00f3th C. D. (2011) Bounds on the maximum multiplicity of some common geometric graphs. In Proc. 28th Symposium on Theoretical Aspects of Computer Science, pp. 637\u2013648. http:\/\/www.stacs-conf.org\/"},{"key":"S096354831300031X_ref11","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(98)00372-0"},{"key":"S096354831300031X_ref17","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/453\/08806"},{"key":"S096354831300031X_ref16","first-page":"219","volume-title":"Handbook of Discrete and Computational Geometry","author":"Pach","year":"2004"},{"key":"S096354831300031X_ref6","first-page":"110","volume-title":"Proc. 18th Annual European Symposium on Algorithms","author":"Buchin","year":"2010"},{"key":"S096354831300031X_ref14","first-page":"303","volume-title":"Thirty Essays on Geometric Graph Theory","author":"Hoffmann"},{"key":"S096354831300031X_ref10","first-page":"13","article-title":"Enumeratio modorum, quibus figurae planae rectilineae per diagonales diuiduntur in triangula.","volume":"7","author":"Euler","year":"1761","journal-title":"Novi Commentarii Academiae Scientiarum Petropolitanae"},{"key":"S096354831300031X_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2006.08.002"},{"key":"S096354831300031X_ref26","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1007\/3-540-63938-1_63","volume-title":"Proc. 5th International Symposium on Graph Drawing","author":"Valtr","year":"1997"},{"key":"S096354831300031X_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-007-0704-5"},{"key":"S096354831300031X_ref5","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1215\/ijm\/1256049011","article-title":"Every planar map is four colorable I: Discharging.","volume":"21","author":"Appel","year":"1977","journal-title":"Illinois J. Math."},{"key":"S096354831300031X_ref13","unstructured":"Heesch H. (1969) Untersuchungen zum Vierfarbenproblem. Hochschulscripten 810\/a\/b, Bibliographisches Institut, Mannheim."},{"key":"S096354831300031X_ref24","first-page":"273","volume-title":"Proc. 22nd ACM Symposium on Computational Geometry","author":"Sharir","year":"2006"},{"key":"S096354831300031X_ref21","first-page":"969","article-title":"The number of spanning trees in a planar graph.","volume":"2","author":"Rote","year":"2005","journal-title":"Oberwolfach Reports"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S096354831300031X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,1]],"date-time":"2022-03-01T22:08:29Z","timestamp":1646172509000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S096354831300031X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,7,25]]},"references-count":26,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2013,11]]}},"alternative-id":["S096354831300031X"],"URL":"https:\/\/doi.org\/10.1017\/s096354831300031x","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,7,25]]}}}