The number of planar graphs and properties of random planar graphs

Omer Gimenez; Marc Noy

doi:10.46298/dmtcs.3354

Omer Gimenez ; Marc Noy - The number of planar graphs and properties of random planar graphs

dmtcs:3354 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms - https://doi.org/10.46298/dmtcs.3354

The number of planar graphs and properties of random planar graphsConference paper

Authors: Omer Gimenez ^1,²; Marc Noy ^1,²

We show an asymptotic estimate for the number of labelled planar graphs on $n$ vertices. We also find limit laws for the number of edges, the number of connected components, and other parameters in random planar graphs.

https://doi.org/10.46298/dmtcs.3354

Source: HAL:hal-01184026v1

Volume: DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms

Section: Proceedings

Published on: January 1, 2005

Imported on: May 10, 2017

Keywords: analytic combinatorics,normal law,Planar graph,random graph,asymptotic enumeration,limit law,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS],[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG],[INFO.INFO-HC]Computer Science [cs]/Human-Computer Interaction [cs.HC]

Bibliographic References

10 Documents citing this article

Maher Afif Younan, 2014, Dynamics and combinatorics of 2 and 3 dimensional triangulations, 10.13097/archive-ouverte/unige:43269.

P. G. Polishchuk;T. I. Madzhidov;A. Varnek, 2013, Estimation of the size of drug-like chemical space based on GDB-17 data, univOAK (4 institutions : Université de Strasbourg, Université de Haute Alsace, INSA Strasbourg, Bibliothèque Nationale et Universitaire de Strasbourg), 27, 8, pp. 675-679, 10.1007/s10822-013-9672-4, https://univoak.eu/islandora/object/islandora%3A112373.

Radoslav Fulek;Noushin Saeedi;Deniz Sarıöz, Springer eBooks, Convex Obstacle Numbers of Outerplanar Graphs and Bipartite Permutation Graphs, pp. 249-261, 2012, 10.1007/978-1-4614-0110-0_13.

Micha Sharir;Adam Sheffer;Emo Welzl, Proceedings of the twenty-sixth annual symposium on Computational geometry, On degrees in random triangulations of point sets, pp. 297-306, 2010, Snowbird Utah USA, 10.1145/1810959.1811009.

Konstantinos Panagiotou, 2009, Blocks in Constrained Random Graphs with Fixed Average Degree, Discrete Mathematics & Theoretical Computer Science, DMTCS Proceedings vol. AK,..., Proceedings, 10.46298/dmtcs.2710, https://doi.org/10.46298/dmtcs.2710.

NICLA BERNASCONI;KONSTANTINOS PANAGIOTOU;ANGELIKA STEGER, 2009, The Degree Sequence of Random Graphs from Subcritical Classes, Repository for Publications and Research Data (ETH Zurich), 18, 5, pp. 647-681, 10.1017/s0963548309990368, https://hdl.handle.net/20.500.11850/21468.

Nicla Bernasconi;Konstantinos Panagiotou;Angelika Steger, Lecture notes in computer science, On the Degree Sequences of Random Outerplanar and Series-Parallel Graphs, pp. 303-316, 2008, 10.1007/978-3-540-85363-3_25.

Nieves Atienza;Natalia de Castro;Carmen Cortés;M. Ángeles Garrido;Clara I. Grima;et al., Lecture notes in computer science, Cover Contact Graphs, pp. 171-182, 2008, 10.1007/978-3-540-77537-9_18, https://doi.org/10.1007/978-3-540-77537-9_18.

Konstantinos Panagiotou;Andreas Weißl, 2007, Properties of Random Graphs via Boltzmann Samplers, Discrete Mathematics & Theoretical Computer Science, DMTCS Proceedings vol. AH,..., Proceedings, 10.46298/dmtcs.3552, https://doi.org/10.46298/dmtcs.3552.

Omer Giménez;Marc Noy;Juan José Rué, 2007, Graph classes with given 3-connected components: asymptotic counting and critical phenomena, Electronic Notes in Discrete Mathematics, 29, pp. 521-529, 10.1016/j.endm.2007.07.080.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 276 times.

This article's PDF has been downloaded 234 times.