Crossing Number of Graphs 读书笔记

Page 3-9

1 The Conjectures of Zarankiewicz and Hills

说明： 个人笔记, 勿过度参考.
正文节选：

1.1 Drawings with Crossings

In his “Perplexities” column for The Strand Magazine, Henry Dudeney posed a puzzle he called “Water, Gas, and Electricity”, accompanied by the illustration in Figure 1.1. Is it possible, he asked, that A, B, and C each have access to (W) ater, (G)as, and (E)lectricity, without their paths crossing?

We would now answer that a solution would require a planar drawing of a K3,3 which we know to be impossible by Kuratowski’s theorem (Appendix A reviews the basics of topological graph theory).

笔记：
这是交叉数的起源问题， $K_{3,3}$K3,3​ 是否存在平面画法？简单的我们可以依据 Kuratowski’s theorem 知道不存在. 当然了，还可以借助一些平面图的不等式去证明.

那么， 何为 Kuratowski’s theorem
A finite graph is planar if and only if it does not contain a subgraph that is a subdivision of K5 (the complete graph on five vertices) or of K3,3 (complete bipartite graph on six vertices)

这里是图的subdivision 定义：
In general, a subdivision of a graph G (sometimes known as an expansion[1]) is a graph resulting from the subdivision of edges in G. The subdivision of some edge e with endpoints {u,v} yields a graph containing one new vertex w, and with an edge set replacing e by two new edges, {u,w} and {w,v}.
For example, the edge e, with endpoints {u,v}:

can be subdivided into two edges, e1 and e2, connecting to a new vertex w:

图的subdivision 是描述图论意义下图的同胚的含义的核心工具.
two graphs $G$G and$G'$G′ are homeomorphic if there is a graph isomorphism from some subdivision of $G$G to some subdivision of $G'$G′.

Henry Dudeney 也意识到这一点，于是他提供了另外一个次一点的方案。

显然： 这是一种退而求其次的办法，虽然各条路的确不交叉了，可是
c和 w 的路经过了A. 这也不符合愿意.
为了避免一些规定上不同导致的没必要的歧义，书本事先给出了详细的公认的规定。

1. In a drawing of a graph, every vertex is assigned a different location, and edges are drawn as simple curves between the locations assigned to their end-points.
   每个顶点放在不同位置.

2. If two edges intersect finitely often, and an edge does not contain a point in its interior, then intersections between two curves are either a common endpoint, a crossing, or a touching point.
   边与边的交点分为3类.