Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, December 14, 2004, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Mihyun Kang (HU Berlin)
An outerplanar graph is a graph that can be embedded in the plane in such a way that every vertex lies on the outer face. We decompose outerplanar graphs along their connectivity structure and derive the equations of the exponential generating functions. With a singularity analysis of these equations we show that the number of labeled outerplanar graphs on n vertices is asymptotically C n-5/2γnn! for constants C, γ = 7.32098. We also show that for constants α, β, the probability of a random outerplanar graph chosen uniformly at random being connected is asymptotically e-α = 0.86166, and that the expected number of edges in a random outerplanar graph on n vertices is asymptotically β n = 1.56251n.
Automatic MiSe System Software Version 1.4803M | admin login