曲線交叉問題是由高斯(Gauss , C. F.)於19世紀提出。
曲線交叉問題(crossing problem)圖論的一個重要問題.設C是一個圓，f是由C到平面上的一個連續映像，記f(C)=Z.對於任何Z上的點P，若存在且僅存在兩個C上的點P,和屍:使得
f<P,)= f<Pz)=P，
則稱屍為Z的一個交叉點.這裡，所考慮的是兩點相交之情形而不考慮多於兩個點之相交.而且，還規定在任何一個交叉點的小鄰域中，若沿Z通過這個交點，則在兩側都會有Z的點.換言之，不考慮相切的情形.設a,b,c,…是Z的所有交叉點.若從Z上任一點屍出發沿著由C所確定的方向經過Z的所有點回到屍，並將所有交叉點依次記下來就得由符號a,b,c,…組成的一個循環序列，則這個序列只與f有關而與P的選取無關.這個序列稱為Z的交叉序列.若一個循環序列中的每個字母均恰出現兩次，則稱它為多面形的.任何曲線的交叉序列都是多面形的;但是，反之一般不成立.所謂曲線交叉問題就是要求刻畫一個多面形序列是某閉曲線的交叉序列.它是由高斯於19世紀首先提出的.高斯為解決這個問題，對於任何一個多面形序列引進了一個圖，稱為它的交叉圖.它的節點為序列中之字母，兩個字母a和b相鄰若且唯若在此序列的兩個a的出現間的一段中，b出現且僅出現一次.高斯猜想，刻畫一個多面形序列為某曲線的交叉序列可僅由其交叉圖的結構性質所決定.德恩(Dehn, M. W.)於1936年解決了曲線相交問題，但他不是沿著高斯猜想的思路，而是在一個多面形序列上引進一些運算將它化為另一個多面形序列.雖然，這個新的序列交叉圖的階比原序列交叉圖的階大一倍;但是，由這個新序列交叉圖的結構性質得到問題的解答較容易.這個方法稱為德恩方法.從算法複雜性而言，德恩方法比高斯猜想要好得多.在德恩之後30餘年，高斯猜想才得到解決.
