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 Library locked




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:




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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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 07:45:12 PM
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section