ในทางคณิตศาสตร์กราฟเชิงทอพอโลยีคือการแสดงกราฟบนระนาบโดยที่จุดยอดของกราฟแทนด้วยจุดที่แตกต่างกัน และขอบแทนด้วยส่วนโค้งจอร์แดน (ส่วนโค้งจอร์แดน ที่เชื่อมต่อกัน ) ที่เชื่อมจุดสองจุดที่สอดคล้องกัน จุดที่แสดงจุดยอดของกราฟและส่วนโค้งที่แสดงขอบของกราฟเรียกว่าจุดยอดและขอบของกราฟเชิงทอพอโลยี โดยทั่วไปแล้วจะถือว่าขอบสองขอบใดๆ ของกราฟเชิงทอพอโลยีจะตัดกันเป็นจำนวนจำกัดครั้ง ไม่มีขอบใดผ่านจุดยอดที่แตกต่างจากจุดปลาย และไม่มีขอบสองขอบใดสัมผัสกัน (โดยไม่ตัดกัน) กราฟเชิงทอพอโลยีเรียกอีกอย่างว่าภาพวาดของกราฟ

กราฟเชิงโทโพโลยีประเภทพิเศษที่สำคัญประเภทหนึ่งคือกราฟเชิงเรขาคณิตซึ่งขอบของกราฟแทนด้วยส่วนของเส้นตรง (บางครั้งคำว่ากราฟเชิงเรขาคณิตก็ถูกใช้ในความหมายที่กว้างกว่าและค่อนข้างคลุมเครือ)

ทฤษฎีกราฟเชิงทอพอโลยีเป็นสาขาหนึ่งของทฤษฎีกราฟซึ่งส่วนใหญ่เกี่ยวข้องกับ คุณสมบัติ เชิงการจัดเรียงของกราฟเชิงทอพอโลยี โดยเฉพาะอย่างยิ่ง รูปแบบการตัดกันของเส้นขอบ ทฤษฎีนี้มีความเกี่ยวข้องอย่างใกล้ชิดกับการวาดกราฟซึ่งเป็นสาขาที่เน้นการประยุกต์ใช้มากกว่า และทฤษฎีกราฟเชิงทอพอโลยีซึ่งมุ่งเน้นไปที่การฝังกราฟลงบนพื้นผิว (กล่าวคือ การวาดภาพโดยไม่มีจุดตัด)

ปัญหาพื้นฐานในทฤษฎีกราฟสุดขั้วคือ: จำนวนขอบสูงสุดที่กราฟที่มี จุดยอด nจุดสามารถมีได้คือเท่าใด หากกราฟนั้นไม่มีกราฟย่อยใดที่อยู่ในกลุ่มกราฟย่อยต้องห้ามที่กำหนดให้ ? ต้นแบบของผลลัพธ์ดังกล่าวคือทฤษฎีบทของ Turánซึ่งมีกราฟย่อยต้องห้ามอยู่หนึ่งกราฟ คือกราฟสมบูรณ์ที่มี จุดยอด kจุด ( โดยที่ kเป็นค่าคงที่) สามารถตั้งคำถามที่คล้ายกันได้สำหรับกราฟเชิงทอพอโลยีและกราฟเชิงเรขาคณิต โดยมีความแตกต่างกันตรงที่ในกรณีนี้การจัดเรียงเชิงเรขาคณิต บางอย่าง ถูกห้าม

ในทางประวัติศาสตร์ ทฤษฎีบทดังกล่าวปรากฏครั้งแรกโดยPaul Erdősซึ่งได้ขยายผลลัพธ์ของHeinz HopfและErika Pannwitz [ ^{2 ] เขา}พิสูจน์ว่าจำนวนขอบสูงสุดที่กราฟเรขาคณิตที่มี จุดยอด n  > 2 สามารถมีได้โดยไม่มีขอบสองขอบที่ไม่เกี่ยวข้อง กัน (ซึ่งไม่สามารถใช้จุดปลายร่วมกันได้) คือn John Conway ตั้งข้อสันนิษฐานว่าข้อความนี้สามารถขยายไปสู่กราฟเชิงทอพอโลยีแบบง่ายได้ กราฟเชิงทอพอโลยีเรียกว่า "แบบง่าย" หากขอบคู่ใด ๆของกราฟนั้นใช้จุดร่วมกันอย่างมากที่สุดเพียงจุดเดียว ซึ่งอาจเป็นจุดปลายหรือจุดภายในร่วมกันที่ขอบทั้งสองตัดกันอย่างถูกต้อง ข้อสันนิษฐานของ Conway สามารถเขียนใหม่ได้ดังนี้: กราฟเชิงทอพอโลยีแบบง่ายที่มี จุดยอด n  > 2 และไม่มีขอบสองขอบที่ไม่เกี่ยวข้องกันจะมีขอบอย่างมากที่สุดnขอบ

ขอบเขตบนเชิงเส้นแรกของจำนวนขอบของกราฟดังกล่าวได้รับการกำหนดโดยLovász et al. ^{[ 3 ]} ขอบเขตบนที่เป็นที่รู้จักดีที่สุด 1.3984 nได้รับการพิสูจน์โดย Fulek และPach ^{[ 4} ] นอกเหนือจากกราฟเรขาคณิตแล้ว สมมติฐาน thrackle ของ Conway เป็นที่ทราบกันว่าเป็นจริงสำหรับกราฟโทโพโลยีx -monotone ^{[ 5 ]}กราฟโทโพโลยีจะเรียกว่าx-monotone ถ้าเส้นแนวตั้งทุก ^เส้นตัดกับขอบทุกเส้นไม่เกินหนึ่งจุด

AlonและErdős ^{[ 6 ]}ได้เริ่มการตรวจสอบการวางนัยทั่วไปของคำถามข้างต้นไปยังกรณีที่การกำหนดค่าต้องห้ามประกอบด้วย ขอบที่ไม่ทับซ้อนกัน kขอบ ( k  ​​> 2) พวกเขาพิสูจน์ว่าจำนวนขอบของกราฟเรขาคณิตที่มี จุดยอด n จุด ซึ่งไม่มีขอบที่ไม่ทับซ้อนกัน 3 ขอบ คือO ( n ) ขอบเขตที่เหมาะสมที่สุดประมาณ 2.5 nถูกกำหนดโดย Černý ^{[ 7 ]} สำหรับค่าk ที่มากขึ้น ขอบเขตบนเชิงเส้นแรกถูกกำหนดโดย Pach และ Töröcsik ^{[ 8 ]}สิ่งนี้ได้รับการปรับปรุงโดย Tóth เป็น^{[ 9 ]} สำหรับจำนวนขอบในกราฟโทโพโลยีแบบง่ายที่ไม่มีขอบ ที่ไม่ทับซ้อนกัน kขอบ มีเพียงขอบเขตบนเท่านั้นที่ทราบ^{[ 10 ]}ซึ่งหมายความว่ากราฟโทโพโลยีแบบง่ายที่สมบูรณ์ทุกกราฟที่มี จุดยอด nจุดจะมีขอบที่ไม่ทับซ้อนกันอย่างน้อยคู่หนึ่ง ซึ่งได้รับการปรับปรุงเป็นโดย Ruiz-Vargas ^{[ 11 ] [ 12 ]}เป็นไปได้ว่าขอบเขตล่างนี้สามารถปรับปรุงเพิ่มเติมเป็นcn ได้ โดยที่c  > 0 เป็นค่าคงที่ ${\displaystyle O(k^{4}n)}$${\displaystyle O(k^{2}n)}$${\displaystyle O(n\log ^{4k-8}n)}$${\displaystyle c{\frac {\log n}{\log \log n}}}$${\displaystyle cn^{{\frac {1}{2}}-\epsilon }}$

จุดร่วมภายในของขอบสองเส้น ซึ่งขอบแรกผ่านจากด้านหนึ่งของขอบที่สองไปยังอีกด้านหนึ่ง เรียกว่า จุดตัดขอบสองเส้นของกราฟเชิงทอ พอโลยี จะตัดกันก็ต่อเมื่อขอบทั้งสองนั้นก่อให้เกิดจุดตัด สำหรับจำนวนเต็มk  > 1 ใดๆ กราฟเชิงทอพอโลยีหรือกราฟเรขาคณิตเรียกว่า k-quasi-planarถ้าไม่มี ขอบตัดกันเป็นคู่ๆ จำนวน kคู่ โดยใช้ศัพท์นี้ ถ้ากราฟเชิงทอพอโลยีเป็น 2-quasi-planar แล้ว กราฟนั้นจะเป็นกราฟระนาบจากสูตรทรงหลายเหลี่ยมของออยเลอร์ จะได้ว่า กราฟระนาบทุก กราฟ ที่มี จุดยอด n  > 2 จะมีขอบอย่างมากที่สุด 3n −  6 ขอบ ดังนั้น กราฟ 2-quasi-planar ทุกกราฟที่มี จุดยอด n  > 2 จะมีขอบอย่างมากที่สุด 3n −  6 ขอบ

^{Pach และคณะ [ 13 ]}ได้ตั้งข้อสันนิษฐาน ว่ากราฟโทโพโลยี แบบ k -quasi-planar ทุก กราฟที่มี n จุดยอดจะมี ขอบไม่เกินc ( k ) n โดยที่ c ( k ) เป็นค่าคงที่ที่ขึ้นอยู่กับk เท่านั้น ข้อสันนิษฐานนี้เป็นที่ทราบกันว่าเป็นจริงสำหรับk  = 3 ^{[ 14 ] [ 15 ]}และk  = 4 ^{[ 16 ]}นอกจากนี้ยังเป็นที่ทราบกันว่าเป็นจริงสำหรับกราฟเรขาคณิตแบบนูน (นั่นคือสำหรับกราฟเรขาคณิตที่มีจุดยอดประกอบเป็นเซตจุดยอดของรูปnเหลี่ยมแบบนูน) ^{[ 17 ]}และสำหรับ กราฟโทโพโลยีแบบ k -quasi-planar ที่มีขอบวาดเป็น เส้นโค้ง x -monotone ซึ่งทั้งหมดตัดกับเส้นตรงแนวตั้ง^{[ 18 ] [ 19 ]} ผลลัพธ์สุดท้ายบ่งชี้ว่า กราฟโทโพโลยี แบบ k -quasi-planar ทุกกราฟที่มีnจุดยอด ซึ่งขอบถูกวาดเป็น เส้นโค้ง x -monotone จะมีขอบไม่เกินc ( k ) n  log  nสำหรับค่าคงที่c ( k ) ที่เหมาะสม สำหรับกราฟเรขาคณิต สิ่งนี้ได้รับการพิสูจน์แล้วก่อนหน้านี้โดย Valtr ^{[ 20 ]}ขอบเขตบนทั่วไปที่ดีที่สุดที่ทราบสำหรับจำนวนขอบของกราฟโทโพโลยีแบบk -quasi-planar คือ^{[ 21 ]} ซึ่งหมายความว่ากราฟโทโพโลยีสมบูรณ์ทุกกราฟที่มี n จุดยอดจะมีขอบตัดกันอย่างน้อยคู่หนึ่ง ซึ่งได้รับการปรับปรุงให้เป็นขอบเขตกึ่งเชิงเส้นในกรณีของกราฟเรขาคณิต^{[ 22 ]}${\displaystyle n\log ^{O(\log k)}n}$${\displaystyle n^{\frac {1}{O(\log \log n)}}}$

นับตั้งแต่Pál Turánได้บัญญัติปัญหาโรงงานอิฐของเขา^{[ 23 ]}ในช่วงสงครามโลกครั้งที่สองการกำหนดหรือการประมาณจำนวนจุดตัดของกราฟได้กลายเป็นหัวข้อที่ได้รับความนิยมในทฤษฎีกราฟและในทฤษฎีอัลกอริทึม^{[ 24 ]}ซึ่งเต็มไปด้วยปัญหาเปิดที่มีชื่อเสียงมายาวนาน เช่นสมมติฐานของ Albertson สมมติฐาน ของHarary-Hill ^{[ 25 ]}หรือปัญหาโรงงานอิฐของ Turán ที่ยังไม่ได้รับ การ แก้ไข ^{[ 26 ] อย่างไรก็ตาม สิ่งพิมพ์ในหัวข้อนี้ (อย่างชัดเจนหรือโดยนัย) ได้ใช้คำจำกัดความของจำนวนจุดตัดที่แตกต่างกันหลายแบบ Pach และ Tóth [ 27 ]}ได้ชี้ให้เห็นถึงเรื่องนี้และได้แนะนำคำศัพท์ต่อไปนี้

จำนวนจุดตัด (ของกราฟG ): จำนวนจุดตัดขั้นต่ำสุดของภาพวาดทั้งหมดของกราฟGบนระนาบ (กล่าวคือ การแสดงกราฟ G ในรูปแบบโทโพโลยีทั้งหมด) โดยมีคุณสมบัติว่าไม่มีเส้นขอบสามเส้นใดผ่านจุดเดียวกัน ใช้สัญลักษณ์ cr( G ) แทน

จำนวนคู่ที่ตัดกัน : จำนวนคู่ของเส้นขอบที่ตัดกันน้อยที่สุดในภาพวาดทั้งหมดของGโดยใช้สัญลักษณ์ pair-cr( G )

จำนวนจุดตัดคี่ : จำนวนขั้นต่ำของคู่เส้นขอบที่ตัดกันเป็นจำนวนครั้งคี่ จากภาพวาดทั้งหมดของกราฟ Gโดยใช้สัญลักษณ์ odd-cr( G )

พารามิเตอร์เหล่านี้ไม่ได้ไม่เกี่ยวข้องกัน มี odd-cr( G ) ≤ pair-cr( G ) ≤ cr( G ) สำหรับทุกกราฟGเป็นที่ทราบกันว่า cr( G ) ≤ 2(odd-cr( G )) ^{2 [ 27 ]}และ^{[ 28 ]} และมีกราฟจำนวนอนันต์ที่ pair-cr( G ) ≠ odd-cr( G ) ^{[ 1 ] [ 29 ]}ยังไม่มีตัวอย่างใดที่ทราบกันว่าจำนวนจุดตัดและจำนวนจุดตัดคู่ไม่เท่ากัน เป็นไปตามทฤษฎีบท Hanani–Tutte ^{[ 30 ] [ 31 ]} ว่า odd-cr( G ) = 0 หมายความว่า cr( G ) = 0 นอกจากนี้ยังเป็นที่ทราบกันว่า odd-cr( G ) =  kหมายความว่า cr( G )=kสำหรับk  = 1, 2, 3 ^{[ 32 ]} พารามิเตอร์กราฟอีกตัวหนึ่งที่ได้รับการวิจัยอย่างดีคือดังต่อไปนี้ ${\displaystyle O(\operatorname {pcr} (G)^{\frac {3}{2}}\log ^{2}\operatorname {pcr} (G))}$

จำนวนจุดตัดเชิงเส้นตรง : จำนวนจุดตัดขั้นต่ำสุดของเส้นตรงทั้งหมดที่ลากผ่านกราฟG บนระนาบ (กล่าวคือ กราฟ G ในรูปแบบเรขาคณิตทั้งหมด) โดยมีคุณสมบัติว่าไม่มีเส้นตรงสามเส้นใดผ่านจุดเดียวกัน ใช้สัญลักษณ์ lin-cr( G ) แทน

ตามคำจำกัดความ จะมี cr( G ) ≤ lin-cr( G ) สำหรับทุกกราฟG Bienstock และ Dean ได้แสดงให้เห็นว่ามีกราฟที่มีจำนวนจุดตัด 4 จุด และมีจำนวนจุดตัดเชิงเส้นตรงขนาดใหญ่ตามอำเภอใจ^{[ 33 ]}

การคำนวณจำนวนจุดตัดเป็นปัญหาNP-complete ^{[ 34 ]}โดยทั่วไป ดังนั้นงานวิจัยจำนวนมากจึงมุ่งเน้นไปที่การประมาณค่าทฤษฎีบทจุดตัดเป็นผลลัพธ์หลักที่ให้ขอบเขตล่างที่ใช้ได้อย่างกว้างขวางสำหรับจำนวนจุดตัด มีรูปแบบและการวางนัยทั่วไปที่น่าสนใจหลายอย่างของทฤษฎีบทจุดตัดสำหรับเส้นโค้งจอร์แดน^{[ 35 ] [ 36 ]}และจำนวนจุดตัดที่เสื่อมสภาพ^{[ 37 ] [ 38 ]}ซึ่งอย่างหลังเชื่อมโยงแนวคิดของจำนวนจุดตัดกับจีนัสของกราฟ

ในทฤษฎีกราฟ แบบดั้งเดิม ผลลัพธ์แบบ Ramseyทั่วไประบุว่า หากเราระบายสีขอบของกราฟสมบูรณ์ขนาดใหญ่พอสมควรด้วยจำนวนสีคงที่ เราจะพบกราฟ ย่อย สีเดียวประเภทใดประเภทหนึ่ง อย่างแน่นอน ^{[ 39 ]}เราสามารถตั้งคำถามที่คล้ายกันสำหรับกราฟเรขาคณิต (หรือกราฟเชิงโทโพโลยี) ยกเว้นว่าตอนนี้เรามองหาโครงสร้างย่อยสีเดียว (สีเดียว) ที่ตรงตามเงื่อนไขทางเรขาคณิตบางประการ^{[ 40 ]} หนึ่งในผลลัพธ์แรกๆ ของประเภทนี้ระบุว่ากราฟเรขาคณิตสมบูรณ์ทุกกราฟที่มีขอบระบายสีด้วยสองสีจะมี ต้นไม้แผ่ขยาย สี เดียว ที่ไม่ตัดกัน^{[ 41 ]}นอกจากนี้ยังเป็นความจริงที่ว่ากราฟเรขาคณิตดังกล่าวทุกกราฟจะมีขอบที่ไม่ซ้ำกันที่มีสีเดียวกัน^{[ 41 ]}การมีอยู่ของเส้นทางสีเดียวที่ไม่ตัดกันที่มีขนาดอย่างน้อยcnโดยที่c  > 0 เป็นค่าคงที่ เป็นปัญหาเปิดที่ ค้างคามานาน เป็นที่ทราบกันเพียงว่ากราฟเรขาคณิตสมบูรณ์ทุกกราฟบน จุดยอด nจุดจะมีเส้นทางสีเดียวที่ไม่ตัดกันที่มีความยาวอย่างน้อย^{[ 42 ]}${\displaystyle \left\lceil {\frac {n+1}{3}}\right\rceil }$${\displaystyle n^{\frac {2}{3}}}$

หากเรามองกราฟเชิงโทโพโลยีเป็นการรับรู้เชิงโทโพโลยีของคอมเพล็กซ์ซิมพลิ เชียล 1 มิติ ก็เป็นเรื่องธรรมชาติที่จะถามว่าปัญหาสุดขั้วและปัญหาประเภทแรมซีย์ข้างต้นจะขยายไปสู่การรับรู้เชิงโทโพโลยีของ คอมเพล็กซ์ซิมพลิเชีย ล d มิติได้อย่างไร มีผลลัพธ์เบื้องต้นบางส่วนในทิศทางนี้ แต่จำเป็นต้องมีการวิจัยเพิ่มเติมเพื่อระบุแนวคิดและปัญหาที่สำคัญ^{[ 43 ] [ 44 ] [ 45 ]}

ซิมเพล็กซ์สองอันที่ ไม่มีจุดยอดร่วมกันจะเรียกว่าตัดกัน หากบริเวณภายในสัมพัทธ์ของซิมเพล็กซ์ทั้งสองมีจุดร่วมกัน เซตของซิมเพล็กซ์ที่มี k  มากกว่า 3 อันจะตัดกันอย่างเข้มข้นหากไม่มีซิมเพล็กซ์สองอันใดที่มีจุดยอดร่วมกัน แต่บริเวณภายในสัมพัทธ์ของซิมเพล็กซ์ทั้งสองมีจุดร่วมกัน

เป็นที่ทราบกันว่าเซตของ ซิมเพล็กซ์มิติ dที่สร้างขึ้นโดย จุด nจุดในโดยไม่มีซิมเพล็กซ์ที่ตัดกันเป็นคู่ สามารถมีซิมเพล็กซ์ได้มากที่สุด และขอบเขตนี้มีความแน่นในเชิงอะ ซิมโทติก ^{[ 46 ]}ผลลัพธ์นี้ได้รับการขยายไปสู่เซตของซิมเพล็กซ์มิติ 2 ใน โดยไม่มีซิมเพล็กซ์ที่ตัดกันอย่างแน่นหนา 3 อัน^{[ 47 ]} หากเราห้าม ซิมเพล็กซ์ที่ตัดกันอย่างแน่นหนา kอัน ขอบเขตบนที่ดีที่สุดที่ทราบคือ[ ^{46 ] สำหรับ}บางค่าผลลัพธ์นี้มาจากทฤษฎีบท Tverberg ที่มีสี[ 48 ^{]ซึ่งห่าง}ไกลจากขอบเขตที่คาดการณ์ไว้^ของ [ ^{46 ]}${\displaystyle \mathbb {R} ^{d}}$${\displaystyle O(n^{d})}$${\displaystyle \mathbb {R} ^{2}}$${\displaystyle O(n^{d+1-\delta })}$${\displaystyle \delta =\delta (k,d)<1}$${\displaystyle O(n^{d})}$

สำหรับk > 1 ที่กำหนดไว้ เราสามารถเลือกซิมเพล็กซ์มิติ d  มากที่สุดที่สร้างขึ้นโดยเซตของ จุด nจุดในที่มีคุณสมบัติว่าไม่มีkจุดใดที่มีจุดภายในร่วมกัน^{[ 46 ] [ 49 ]}ซึ่งมีความแน่นในเชิงอะซิมโทติก ${\displaystyle O(n^{\lceil {\frac {d}{2}}\rceil })}$${\displaystyle \mathbb {R} ^{d}}$

สามเหลี่ยมสองรูปในจะเรียกว่าเกือบไม่ทับซ้อนกันหากสามเหลี่ยมทั้งสองไม่ทับซ้อนกัน หรือหากมีจุดยอดร่วมกันเพียงจุดเดียว เป็นปัญหาเก่าแก่ของGil Kalaiและคนอื่นๆ ที่จะตัดสินว่าจำนวนสามเหลี่ยมเกือบไม่ทับซ้อนกันที่มากที่สุดที่สามารถเลือกได้จากเซตจุดยอดnจุดใน นั้นคือ หรือไม่ เป็นที่ทราบกันว่ามีเซตของ จุด nจุด ซึ่งจำนวนนี้อย่างน้อยที่สุดสำหรับค่าคงที่c  > 0 ที่เหมาะสม ^{[ 50 ]}${\displaystyle \mathbb {R} ^{3}}$${\displaystyle \mathbb {R} ^{3}}$${\displaystyle o(n^{2})}$${\displaystyle cn^{\frac {3}{2}}}$