Proceedings Article, Paper @InProceedings Beitrag in Tagungsband, Workshop

 Show entries of: this year (2019) | last year (2018) | two years ago (2017) | Notes URL
 Action: login to update Options: Library locked Goto entry point

 Author, Editor
 Author(s): Panagiotou, Konstantinos Steger, Angelika dblp dblp Not MPG Author(s): Steger, Angelika
 Editor(s): Matthieu, Claire dblp Not MPII Editor(s): Matthieu, Claire
 BibTeX cite key*: PanagiotouSteger2008

 Title, Booktitle
 Title*: Maximal Biconnected Subgraphs of Random Planar Graphs Booktitle*: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009)

 Event, URLs
 URL of the conference: http://www.siam.org/meetings/da09/ URL for downloading the paper: http://www.siam.org/proceedings/soda/2009/SODA09_048_panagiotouk.pdf Event Address*: New York, NY, USA Language: English Event Date* (no longer used): Organization: ACM, SIAM Event Start Date: 4 January 2009 Event End Date: 6 January 2009

 Publisher
 Name*: ACM URL: Address*: New York, NY Type:

 Vol, No, Year, pp.
 Series:
 Volume: Number: Month: Pages: 432-440 Year*: 2009 VG Wort Pages: ISBN/ISSN: Sequence Number: DOI:

 (LaTeX) Abstract: Let $\mathcal{C}$ be a class of labeled connected graphs, and let $C_n$ be a graph drawn uniformly at random from graphs in $\mathcal{C}$ that contain exactly $n$ vertices. Denote by~$b(\ell;\, C_n)$ the number of blocks (i.e.\ maximal biconnected subgraphs) of~$C_n$ that contain exactly~$\ell$ vertices, and let~$lb(C_n)$ be the number of vertices in a largest block of~$C_n$. We show that under certain general assumptions on~$\mathcal{C}$, $C_n$ belongs with high probability to one of the following categories: \begin{itemize} \item[(1)] $lb(C_n) \sim cn$, for some explicitly given $c = c(\mathcal{C})$, and the second largest block is of order $n^{\alpha}$, where $1 > \alpha = \alpha(\mathcal{C})$, or \item[(2)] $lb(C_n) = \mathcal{O}(\log n)$, i.e., all blocks contain at most logarithmically many vertices. \end{itemize} Moreover, in both cases we show that the quantity $b(\ell;\, C_n)$ is concentrated for all $\ell$, and we determine its expected value. As a corollary we obtain that the class of planar graphs belongs to category (1). In contrast to that, outerplanar and series-parallel graphs belong to category~(2). Keywords: Graphs with Constraints, Planar Graphs, Random Structures Download Access Level: Public

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@INPROCEEDINGS{PanagiotouSteger2008,
AUTHOR = {Panagiotou, Konstantinos and Steger, Angelika},
EDITOR = {Matthieu, Claire},
TITLE = {Maximal Biconnected Subgraphs of Random Planar Graphs},
BOOKTITLE = {Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009)},
PUBLISHER = {ACM},
YEAR = {2009},
ORGANIZATION = {ACM, SIAM},
PAGES = {432--440},
ADDRESS = {New York, NY, USA},
}