K2,4,n之交叉數

The Crossing Number of K2,4,n

蘇承祖(Chen-Chu Su)

指導教授 ： 陳文進

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2010年)

https://doi.org/10.6342/NTU.2010.02641

摘要

交叉數是一個圖，在平面上所有的畫法中，可以畫出最小的交叉數。在這篇論
文，根據Kleitman證明完全二分圖的結果，我們證明了對於所有的n， K2,4,n這個
完全三分圖的交叉數。最後，我們提出了關於K2,m,n交叉數的猜想。

關鍵字

交叉數 ； 圖 ； 完全二分圖 ； 完全三分圖 ； NP完備

並列摘要

The crossing Number $cr(G)$ of a graph $G$ is the smallest crossing number among all drawings of $G$ in the plane.
In this paper, we determine the crossing number of the tripartite graph $K_{2,4,n}$ for any integer $n$. Our proof depends on Kleitman's results for the complete bipartite graphs.
At last, we propose a conjecture of the crossing number of $K_{2,m,n}$.

並列關鍵字

Crossing number ； graph ； complete bipartite graph ； complete tripartite graph ； NP-complete

參考文獻

[1] Daniel J. Kleitman. The crossing number of K5,n. J. Combinatorial Theory, 9:315–

323, 1970.

[2] M. R. Garey and D. S. Johnson. Crossing number is NP-complete. SIAM J. Algebraic

Discrete Methods, 4(3):312–316, 1983.

[3] Ken-ichi Kawarabayashi and Bruce Reed. Computing crossing number in linear