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. On the number of ser ...
Conference paper

On the number of series parallel and outerplanar graphs

Manuel Bodirsky (1), Omer Gimenez (2), Mihyun Kang (1), Marc Noy (2)
(1) Department of Computer Science [Berlin]
(2) Departament de Matemàtica Aplicada II
Download article
Open on HAL
Imported on
May 10, 2017
Published on
December 31, 2004
Last modified on
March 31, 2025
Volume 0
DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Proceedings
DOI
10.46298/dmtcs.3451
License
https://about.hal.science/hal-authorisation-v1
Indicators
758
Views
485
Downloads

On the number of series parallel and outerplanar graphs

Manuel Bodirsky (1), Omer Gimenez (2), Mihyun Kang (1), Marc Noy (2)
(1) Department of Computer Science [Berlin]
(2) Departament de Matemàtica Aplicada II
Abstract
We show that the number $g_n$ of labelled series-parallel graphs on $n$ vertices is asymptotically $g_n \sim g \cdot n^{-5/2} \gamma^n n!$, where $\gamma$ and $g$ are explicit computable constants. We show that the number of edges in random series-parallel graphs is asymptotically normal with linear mean and variance, and that the number of edges is sharply concentrated around its expected value. Similar results are proved for labelled outerplanar graphs.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
  • Series parallel graph
  • outerplanar graph
  • random graph
  • asymptotic enumeration
  • limit law
  • normal law
  • analytic combinatorics
Cited by

Source: OpenCitations

  • Random Graphs from a Minor-Closed Class

    Combinatorics Probability Computing

    Authors : COLIN McDIARMID

    Journal reference : Volume 18, 2009, pp. 583-599

    DOI : 10.1017/s0963548309009717

  • The Degree Sequence of Random Graphs from Subcritical Classes

    Combinatorics Probability Computing

    Authors : NICLA BERNASCONI, KONSTANTINOS PANAGIOTOU ORCID, ANGELIKA STEGER ORCID

    Journal reference : Volume 18, 2009, pp. 647-681

    DOI : 10.1017/s0963548309990368

  • Random cubic planar graphs

    Random Structures and Algorithms

    Authors : Manuel Bodirsky ORCID, Mihyun Kang ORCID, Mike Löffler, Colin McDiarmid

    Journal reference : Volume 30, 2006, pp. 78-94

    DOI : 10.1002/rsa.20149

  • Random graphs on surfaces

    Journal of Combinatorial Theory Series B

    Authors : Colin McDiarmid

    Journal reference : Volume 98, 2008, pp. 778-797

    DOI : 10.1016/j.jctb.2007.11.006

  • Graph classes with given 3-connected components: asymptotic counting and critical phenomena

    Electronic Notes in Discrete Mathematics

    Authors : Omer Giménez, Marc Noy ORCID, Juan José Rué ORCID

    Journal reference : Volume 29, 2007, pp. 521-529

    DOI : 10.1016/j.endm.2007.07.080

  • On the Degree Sequences of Random Outerplanar and Series-Parallel Graphs

    Lecture notes in computer science

    Authors : Nicla Bernasconi, Konstantinos Panagiotou ORCID, Angelika Steger ORCID

    Journal reference : Volume , 2008, pp. 303-316

    DOI : 10.1007/978-3-540-85363-3_25

  • 3-Connected Cores In Random Planar Graphs

    Combinatorics Probability Computing

    Authors : NIKOLAOS FOUNTOULAKIS ORCID, KONSTANTINOS PANAGIOTOU ORCID

    Journal reference : Volume 20, 2011, pp. 381-412

    DOI : 10.1017/s0963548310000532

  • Connectivity for Bridge-Addable Monotone Graph Classes

    Combinatorics Probability Computing

    Authors : L. ADDARIO-BERRY ORCID, C. MCDIARMID, B. REED ORCID

    Journal reference : Volume 21, 2012, pp. 803-815

    DOI : 10.1017/s0963548312000272

  • Sampling Unlabeled Biconnected Planar Graphs

    Lecture notes in computer science

    Authors : Manuel Bodirsky ORCID, Clemens Gröpl, Mihyun Kang ORCID

    Journal reference : Volume , 2005, pp. 593-603

    DOI : 10.1007/11602613_60
Preview
Loading PDF preview...