MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Panagiotou, Konstantinos
Steger, Angelika		dblp
dblp
Not MPG Author(s):
Steger, Angelika
Editor(s):
Matthieu, Clairedblp
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
Conference URL::
http://www.siam.org/meetings/da09/
Downloading URL:
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:
Note, Abstract, ©
(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},
}

Entry last modified by Anja Becker, 03/09/2010
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]		Created
02/12/2009 19:45:12
Revisions
3.
2.
1.
0.
Editor(s)
Anja Becker
Konstantinos Panagiotou
Konstantinos Panagiotou
Konstantinos Panagiotou
Edit Dates
09.03.2010 14:16:49
04/07/2009 06:45:43 PM
02/16/2009 11:02:22 AM
02/12/2009 07:45:12 PM