Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Degree distribution ...
Conference paper

Degree distribution in random planar graphs

Michael Drmota (1), Omer Gimenez (2) (3) (4), Marc Noy (2) (3) (4)
(1) Institut für Diskrete Mathematik und Geometrie [Wien]
(2) Universitat Politècnica de Catalunya [Barcelona]
(3) Universitat Politècnica de Catalunya = Université polytechnique de Catalogne [Barcelona]
(4) Universitat Politècnica de Catalunya = Université polytechnique de Catalogne = Polytechnic University of Catalunya [Barcelona]
Download article
Open on HAL
Imported on
May 10, 2017
Published on
December 31, 2007
Last modified on
March 31, 2025
Volume
DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science
Proceedings
DOI
10.46298/dmtcs.3562
License
https://about.hal.science/hal-authorisation-v1
Indicators
641
Views
1036
Downloads

Degree distribution in random planar graphs

Michael Drmota (1), Omer Gimenez (2) (3) (4), Marc Noy (2) (3) (4)
(1) Institut für Diskrete Mathematik und Geometrie [Wien]
(2) Universitat Politècnica de Catalunya [Barcelona]
(3) Universitat Politècnica de Catalunya = Université polytechnique de Catalogne [Barcelona]
(4) Universitat Politècnica de Catalunya = Université polytechnique de Catalogne = Polytechnic University of Catalunya [Barcelona]
Abstract
We prove that for each $k \geq 0$, the probability that a root vertex in a random planar graph has degree $k$ tends to a computable constant $d_k$, and moreover that $\sum_k d_k =1$. The proof uses the tools developed by Gimènez and Noy in their solution to the problem of the asymptotic enumeration of planar graphs, and is based on a detailed analysis of the generating functions involved in counting planar graphs. However, in order to keep track of the degree of the root, new technical difficulties arise. We obtain explicit, although quite involved expressions, for the coefficients in the singular expansions of interest, which allow us to use transfer theorems in order to get an explicit expression for the probability generating function $p(w)=\sum_k d_k w^k$. From the explicit expression for $p(w)$ we can compute the $d_k$ to any degree of accuracy, and derive asymptotic estimates for large values of $k$.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • [MATH.MATH-DS]Mathematics [math]/Dynamical Systems [math.DS]
  • [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
  • Planar graph
  • Random graph
  • Degree distribution
Cited by

Source: OpenCitations

  • Asymptotic Study of Subcritical Graph Classes

    arXiv (Cornell University)

    Authors : Michael Drmota, Éric Fusy, Mihyun Kang, Veronika Kraus, Juanjo Rué

    Journal reference : Volume 25, 2011, pp. 1615-1651

    DOI : 10.1137/100790161

  • Local Convergence of Random Planar Graphs

    Trends in mathematics

    Authors : Benedikt Stufler

    Journal reference : Volume , 2021, pp. 57-63

    DOI : 10.1007/978-3-030-83823-2_10

  • Analytic Combinatorics on Random Graphs

    Analysis of Complex Networks

    Authors : Michael Drmota ORCID, Bernhard Gittenberger ORCID

    Journal reference : Volume , 2009, pp. 425-450

    DOI : 10.1002/9783527627981.ch17

  • A Central Limit Theorem for the Number of Degree-k Vertices in Random Maps

    Algorithmica

    Authors : Michael Drmota ORCID, Konstantinos Panagiotou ORCID

    Journal reference : Volume 66, 2013, pp. 741-761

    DOI : 10.1007/s00453-013-9751-x

  • Uniform random sampling of planar graphs in linear time

    Random Structures and Algorithms

    Authors : Éric Fusy ORCID

    Journal reference : Volume 35, 2009, pp. 464-522

    DOI : 10.1002/rsa.20275

  • Extremal statistics on non-crossing configurations

    Discrete Mathematics

    Authors : Michael Drmota, Anna de Mier ORCID, Marc Noy ORCID

    Journal reference : Volume 327, 2014, pp. 103-117

    DOI : 10.1016/j.disc.2014.03.016

  • Phase transitions in graphs on orientable surfaces

    Random Structures and Algorithms

    Authors : Mihyun Kang ORCID, Michael Moßhammer, Philipp Sprüssel ORCID

    Journal reference : Volume 56, 2020, pp. 1117-1170

    DOI : 10.1002/rsa.20900

  • Asymptotic Properties of Some Minor-Closed Classes of Graphs

    arXiv (Cornell University)

    Authors : MIREILLE BOUSQUET-MÉLOU ORCID, KERSTIN WELLER

    Journal reference : Volume 23, 2014, pp. 749-795

    DOI : 10.1017/s0963548314000303

  • The Degree Distribution of Random Planar Graphs

    Lecture notes in geoinformation and cartography

    Authors : Michael Drmota ORCID

    Journal reference : Volume , 2009, pp. 189-199

    DOI : 10.1007/978-3-540-88244-2_13

  • Local convergence of random planar graphs

    Journal of the European Mathematical Society

    Authors : Benedikt Stufler ORCID

    Journal reference : Volume 25, 2021, pp. 1-73

    DOI : 10.4171/jems/1174

  • Random graphs from restricted classes

    Cambridge University Press eBooks

    Authors : Konstantinos Panagiotou ORCID

    Journal reference : Volume , 2016, pp. 28-66

    DOI : 10.1017/cbo9781316479988.003

  • Graph classes with given 3‐connected components: Asymptotic enumeration and random graphs

    Random Structures and Algorithms

    Authors : Omer Giménez, Marc Noy ORCID, Juanjo Rué ORCID

    Journal reference : Volume 42, 2012, pp. 438-479

    DOI : 10.1002/rsa.20421

  • Concentration of maximum degree in random planar graphs

    Journal of Combinatorial Theory Series B

    Authors : Mihyun Kang ORCID, Michael Missethan ORCID

    Journal reference : Volume 156, 2022, pp. 310-342

    DOI : 10.1016/j.jctb.2022.05.005

  • The maximum degree of random planar graphs

    Proceedings of the London Mathematical Society

    Authors : M. Drmota ORCID, O. Giménez, M. Noy ORCID, K. Panagiotou ORCID, A. Steger ORCID

    Journal reference : Volume 109, 2014, pp. 892-920

    DOI : 10.1112/plms/pdu024

  • Random Planar Maps and Graphs with Minimum Degree Two and Three

    The Electronic Journal of Combinatorics

    Authors : Marc Noy ORCID, Lander Ramos

    Journal reference : Volume 25, 2018, pp.

    DOI : 10.37236/7640

  • The Evolution of Random Graphs on Surfaces

    arXiv (Cornell University)

    Authors : Chris Dowden, Mihyun Kang ORCID, Philipp Sprüssel ORCID

    Journal reference : Volume 32, 2017, pp. 367-373

    DOI : 10.1016/j.endm.2017.06.061

  • Limits of random tree-like discrete structures

    Probability Surveys

    Authors : Benedikt Stufler ORCID

    Journal reference : Volume 17, 2020, pp.

    DOI : 10.1214/19-ps338

  • Composition Schemes: q-Enumerations and Phase Transitions in Gibbs Models

    arXiv (Cornell University)

    Authors : Banderier, Kuba, Wagner, Wallner

    Journal reference : Volume , 2023, pp.

    DOI : 10.4230/lipics.aofa.2024.7

  • Random planar graphs with minimum degree two and three

    Scuola Normale Superiore eBooks

    Authors : Marc Noy ORCID, Lander Ramos

    Journal reference : Volume , 2013, pp. 251-258

    DOI : 10.1007/978-88-7642-475-5_41

  • The Maximum Degree of Series-Parallel Graphs

    Combinatorics Probability Computing

    Authors : MICHAEL DRMOTA, OMER GIMÉNEZ, MARC NOY ORCID

    Journal reference : Volume 20, 2011, pp. 529-570

    DOI : 10.1017/s0963548311000198

  • Maximum degree in minor-closed classes of graphs

    European Journal of Combinatorics

    Authors : Omer Giménez, Dieter Mitsche, Marc Noy ORCID

    Journal reference : Volume 55, 2016, pp. 41-61

    DOI : 10.1016/j.ejc.2016.02.001
Preview
Loading PDF preview...