





















In a simple drawing of a graph every pair of edges intersect each other in at most one point, which is either a common endvertex or a proper crossing. For each positive integer $n$, Negami identified a drawing $B_n$ of the complete bipartite graph $K_{n,n}$, and proved that if $N$ is sufficiently large, then every drawing of $K_{N,N}$ contains a drawing of $K_{n,n}$ weakly isomorphic to $B_n$. Thus $B_n$ is (up to weak isomorphism) the only {\em unavoidable} drawing of $K_{n,n}$. We extend this result to complete multipartite graphs, characterizing their unavoidable drawings.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。