On properties of random dissections and triangulations |
| |
Authors: | Nicla Bernasconi Konstantinos Panagiotou Angelika Steger |
| |
Institution: | 1. Institute for Theoretical Computer Science, ETH Zürich, Universit?tsstrasse 6, CH-8092, Zürich, Switzerland
|
| |
Abstract: | In this work we study properties of random graphs that are drawn uniformly at random from the class consisting of biconnected
outerplanar graphs, or equivalently dissections of large convex polygons. We obtain very sharp concentration results for the
number of vertices of any given degree, and for the number of induced copies of a given fixed graph. Our method gives similar
results for random graphs from the class of triangulations of convex polygons. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|