solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看3649次
Convex drawings of the complete graph: topology meets geometry. (arXiv:1712.06380v1 [math.CO])
来源于:arXiv
In this work, we introduce and develop a theory of convex drawings of the
complete graph $K_n$ in the sphere. A drawing $D$ of $K_n$ is convex if, for
every 3-cycle $T$ of $K_n$, there is a closed disc $\Delta_T$ bounded by $D[T]$
such that, for any two vertices $u,v$ with $D[u]$ and $D[v]$ both in
$\Delta_T$, the entire edge $D[uv]$ is also contained in $\Delta_T$.
As one application of this perspective, we consider drawings containing a
non-convex $K_5$ that has restrictions on its extensions to drawings of $K_7$.
For each such drawing, we use convexity to produce a new drawing with fewer
crossings. This is the first example of local considerations providing
sufficient conditions for suboptimality. In particular, we do not compare the
number of crossings {with the number of crossings in} any known drawings. This
result sheds light on Aichholzer's computer proof (personal communication)
showing that, for $n\le 12$, every optimal drawing of $K_n$ is convex.
Convex drawings are characte 查看全文>>