论文标题
中小型图的平面性的临界点
A Tipping Point for the Planarity of Small and Medium Sized Graphs
论文作者
论文摘要
本文介绍了对小中大小随机图的密度与平面性之间关系之间关系的经验研究。众所周知，当顶点数量趋于无限时，边缘密度d = 0.5之间的平面和非平面度之间存在急剧过渡。但是，这种渐近特性无法阐明尺寸减小的图表发生了什么。我们表明，中小型图也表现出了出乎意料的尖锐过渡。另外，我们表明，对于某些平面性的限制或放松，可以观察到相同的“临界点”行为（我们分别考虑了外平性和接近平面性）。
This paper presents an empirical study of the relationship between the density of small-medium sized random graphs and their planarity. It is well known that, when the number of vertices tends to infinite, there is a sharp transition between planarity and non-planarity for edge density d=0.5. However, this asymptotic property does not clarify what happens for graphs of reduced size. We show that an unexpectedly sharp transition is also exhibited by small and medium sized graphs. Also, we show that the same "tipping point" behavior can be observed for some restrictions or relaxations of planarity (we considered outerplanarity and near-planarity, respectively).
