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: [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], [en] analytic combinatorics, normal law, Planar graph, random graph, asymptotic enumeration, limit law

Bibliographic References

10 Documents citing this article

Maher Afif Younan, 2014, Dynamics and combinatorics of 2 and 3 dimensional triangulations, Archive ouverte UNIGE (University of Geneva), 10.13097/archive-ouverte/unige:43269, https://archive-ouverte.unige.ch/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, Journal of Computer-Aided Molecular Design, 27, 8, pp. 675-679, 10.1007/s10822-013-9672-4.

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

Micha Sharir;Adam Sheffer;Emo Welzl, 2010, On degrees in random triangulations of point sets, Proceedings of the twenty-sixth annual symposium on Computational geometry, pp. 297-306, 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, Combinatorics Probability Computing, 18, 5, pp. 647-681, 10.1017/s0963548309990368, https://doi.org/10.1017/s0963548309990368.

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

Nieves Atienza;Natalia de Castro;Carmen Cortés;M. Ángeles Garrido;Clara I. Grima;et al., 2008, Cover Contact Graphs, Lecture notes in computer science, pp. 171-182, 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 363 times.

This article's PDF has been downloaded 373 times.