ในทฤษฎีกราฟซึ่งเป็นสาขาหนึ่งของคณิตศาสตร์กราฟยอดแหลม (apex graph)คือกราฟที่สามารถทำให้เป็นกราฟระนาบได้โดยการลบจุดยอด เพียงจุดเดียว จุดยอดที่ถูกลบเรียกว่ายอดแหลมของกราฟ ที่ ใช้คำว่า "ยอด แหลม " ไม่ใช่ "ยอด แหลมเดียว" เพราะกราฟยอดแหลมอาจมียอดแหลมมากกว่าหนึ่งจุด ตัวอย่างเช่น ในกราฟที่ไม่เป็นระนาบขั้นต่ำK₅หรือ_K₃ , _₃ทุกจุดยอดเป็นยอดแหลม กราฟยอดแหลมรวมถึงกราฟที่เป็นระนาบอยู่แล้ว ซึ่งในกรณีนี้ทุกจุดยอดก็เป็นยอดแหลมเช่นกันกราฟว่าง (null graph)ก็ถูกนับว่าเป็นกราฟยอดแหลมด้วย แม้ว่าจะไม่มีจุดยอดให้ลบก็ตาม

กราฟ Apex ปิดภายใต้การดำเนินการของการใช้ไมเนอร์และมีบทบาทในแง่มุมอื่นๆ ของทฤษฎีไมเนอร์กราฟหลายประการ ได้แก่การฝังแบบไร้ลิงก์ [ ^{1 ] ข้อ} สันนิษฐาน ของHadwiger ^{[ 2 ]}กราฟที่ลดรูป YΔY ได้^{[ 3 ]}และความสัมพันธ์ระหว่างความกว้างของต้นไม้และเส้นผ่านศูนย์กลางของกราฟ^{[ 4 ]}

กราฟเอเพ็กซ์จะปิดภายใต้การดำเนินการของการหาไมเนอร์ : การหดตัวของขอบใดๆ หรือการลบขอบหรือจุดยอดใดๆ จะนำไปสู่กราฟเอเพ็กซ์อีกกราฟหนึ่ง เพราะถ้าGเป็นกราฟเอเพ็กซ์ที่มีเอเพ็กซ์vการหดตัวหรือการลบใดๆ ที่ไม่เกี่ยวข้องกับvจะรักษาความเป็นระนาบของกราฟที่เหลืออยู่ เช่นเดียวกับการลบขอบใดๆ ที่เชื่อมต่อกับvหากขอบที่เชื่อมต่อกับvถูกหดตัว ผลกระทบต่อกราฟที่เหลืออยู่จะเทียบเท่ากับการลบจุดปลายอีกด้านของขอบ และหากvถูกลบออก จุดยอดอื่นใดก็สามารถเลือกเป็นเอเพ็กซ์ได้^{[ 5 ]}

ตามทฤษฎีบทของ Robertson–Seymourเนื่องจากกราฟยอด (apex graphs) เป็นกลุ่มกราฟปิดไมเนอร์ (minor-closed family) กราฟยอดจึงมีลักษณะกราฟต้องห้าม (forbidden graph characterization ) มีเพียงกราฟจำนวนจำกัดเท่านั้นที่ไม่ใช่กราฟยอดและไม่มีกราฟที่ไม่ใช่กราฟยอดเป็นไมเนอร์ กราฟเหล่านี้เป็นไมเนอร์ต้องห้ามเนื่องจากคุณสมบัติของการเป็นกราฟยอด กราฟอื่นใดGจะเป็นกราฟยอดก็ต่อเมื่อไม่มีไมเนอร์ต้องห้ามใดเป็นไมเนอร์ของGไมเนอร์ต้องห้ามเหล่านี้รวมถึงกราฟเจ็ดกราฟของตระกูล Petersen กราฟที่ไม่เชื่อมต่อกันสามกราฟที่เกิดจากการรวมกันแบบไม่ทับซ้อนกันของ K ₅และK _3,3สองกราฟและกราฟอื่น ๆ อีกมากมาย อย่างไรก็ตาม คำอธิบายที่สมบูรณ์ของกราฟเหล่านี้ยังคงไม่เป็นที่รู้จัก^{[ 5 ] [ 6 ]}

แม้ว่าชุดย่อยที่ต้องห้ามทั้งหมดจะยังไม่เป็นที่รู้จัก แต่ก็สามารถทดสอบได้ว่ากราฟที่กำหนดเป็นกราฟยอดหรือไม่ และถ้าเป็นเช่นนั้น ก็สามารถหายอดสำหรับกราฟได้ในเวลาเชิงเส้นโดยทั่วไปแล้ว สำหรับค่าคงที่k ใดๆ ก็สามารถระบุได้ในเวลาเชิงเส้น กราฟ k-ยอดซึ่งเป็นกราฟที่การลบชุดจุดยอดที่เลือกอย่างระมัดระวังไม่เกินkจุดจะนำไปสู่กราฟระนาบ^{[ 7 ]} อย่างไรก็ตาม หากkเป็นตัวแปร ปัญหาจะเป็นNP- complete ^{[ 8 ]}

กราฟยอดทุกกราฟมีจำนวนสีไม่เกินห้าสี: กราฟระนาบพื้นฐานต้องการสีไม่เกินสี่สีตามทฤษฎีบทสี่สีและจุดยอดที่เหลือต้องการสีเพิ่มเติมไม่เกินหนึ่งสีโรเบิร์ตสัน ซีมัวร์ และโทมัส (1993a)ใช้ข้อเท็จจริงนี้ในการพิสูจน์กรณีk = 6ของข้อสันนิษฐานของแฮดวิเกอร์ซึ่งเป็นข้อความที่ว่ากราฟ 6 สีทุกกราฟมีกราฟสมบูรณ์K₆เป็นกราฟย่อย: พวกเขาแสดงให้เห็นว่าตัวอย่างค้าน ขั้นต่ำใดๆ ต่อข้อสันนิษฐานจะต้องเป็นกราฟยอด แต่เนื่องจากไม่มีกราฟยอด 6 สี ตัวอย่างค้านดังกล่าวจึงไม่สามารถมีอยู่ _ได้

Jørgensen (1994) ตั้งข้อสันนิษฐานว่ากราฟ ที่เชื่อมต่อกัน 6 จุดยอดทุกกราฟที่ไม่มีK ₆เป็นไมเนอร์จะต้องเป็นกราฟยอด หากข้อสันนิษฐานนี้ได้รับการพิสูจน์ ผลลัพธ์ของ Robertson–Seymour–Thomas เกี่ยวกับข้อสันนิษฐานของ Hadwiger จะเป็นผลลัพธ์โดยตรง^{[ 2 ]}ข้อสันนิษฐานของ Jørgensen ยังไม่ได้รับการพิสูจน์^{[ 9 ]}อย่างไรก็ตาม หากเป็นเท็จ ก็จะมีตัวอย่างค้านเพียงจำนวนจำกัดเท่านั้น^{[ 10 ]}

ตระกูลกราฟFมีtreewidth เฉพาะที่จำกัดหากกราฟในFเป็นไปตามความสัมพันธ์เชิงฟังก์ชันระหว่างเส้นผ่านศูนย์กลางและtreewidthกล่าวคือ มีฟังก์ชันf อยู่ ซึ่ง treewidth ของกราฟที่มีเส้นผ่านศูนย์กลางdในFจะมีค่าไม่เกินf ( d )กราฟยอดไม่มี treewidth เฉพาะที่จำกัด: กราฟยอดที่เกิดจากการเชื่อมต่อจุดยอดกับทุกจุดยอดของกราฟกริดn × n มี treewidth nและเส้นผ่านศูนย์กลาง 2 ดังนั้น treewidth จึงไม่ถูกจำกัดด้วยฟังก์ชันของเส้นผ่านศูนย์กลางสำหรับกราฟเหล่านี้ อย่างไรก็ตาม กราฟยอดมีความเชื่อมโยงอย่างใกล้ชิดกับ treewidth เฉพาะที่จำกัด: ตระกูลกราฟปิดไมเนอร์Fที่มี treewidth เฉพาะที่จำกัดคือตระกูลที่มีกราฟยอดเป็นหนึ่งในไมเนอร์ต้องห้าม^{[ 4 ]}ตระกูลกราฟปิดไมเนอร์ที่มีกราฟยอดเป็นหนึ่งในไมเนอร์ต้องห้ามเรียกว่าapex-minor- free ด้วยคำศัพท์นี้ ความเชื่อมโยงระหว่างกราฟยอดและค่า treewidth เฉพาะที่สามารถกล่าวใหม่ได้ว่า ตระกูลกราฟที่ปราศจากไมเนอร์ที่ยอดนั้นเหมือนกับตระกูลกราฟที่ปิดด้วยไมเนอร์และมีค่า treewidth เฉพาะที่จำกัด

แนวคิดของความกว้างต้นไม้เฉพาะที่จำกัดเป็นพื้นฐานของทฤษฎีมิติคู่และอนุญาตให้แก้ปัญหาเชิงอัลกอริทึมจำนวนมากบนกราฟที่ไม่มีเอเพ็กซ์ไมเนอร์ได้อย่างแม่นยำด้วยอัลกอริทึมเวลาพหุนามหรือ อัลกอริทึม ที่จัดการได้ด้วยพารามิเตอร์คงที่หรือประมาณค่าโดยใช้แผนการประมาณค่าเวลาพหุนาม [ ^{11 ] ตระกูล}กราฟที่ไม่มีเอเพ็กซ์ไมเนอร์เป็นไปตามทฤษฎีบทโครงสร้างกราฟ เวอร์ชันที่แข็งแกร่งขึ้น ซึ่งนำไปสู่อัลกอริทึมการประมาณค่าเพิ่มเติมสำหรับการระบายสีกราฟและปัญหาพนักงานขายเดินทาง^{[ 12 ]}อย่างไรก็ตาม ผลลัพธ์บางส่วนเหล่านี้ยังสามารถขยายไปยังตระกูลกราฟปิดไมเนอร์ใดๆ ผ่านทฤษฎีบทโครงสร้างที่เชื่อมโยงกับกราฟที่ไม่มีเอเพ็กซ์ไมเนอร์^{[ 13 ]}

ถ้าGเป็นกราฟยอดแหลมที่มีจุดยอดvและτคือจำนวนหน้าขั้นต่ำที่จำเป็นในการครอบคลุมเพื่อนบ้านทั้งหมดของvในการฝังแบบระนาบของG \ { v }แล้วGสามารถฝังลงบนพื้นผิวสองมิติที่มีจีนัสτ – 1ได้ โดยการเพิ่มสะพานจำนวนนั้นลงในการฝังแบบระนาบ เชื่อมต่อหน้าทั้งหมดที่vต้องเชื่อมต่อเข้าด้วยกัน ตัวอย่างเช่น การเพิ่มจุดยอดเดียวลงในกราฟนอกระนาบ (กราฟที่มีτ = 1 ) จะสร้างกราฟระนาบ เมื่อG \ { v }เป็นกราฟ 3-เชื่อมต่อ ขอบเขตนี้จะอยู่ภายในปัจจัยคงที่ของค่าที่เหมาะสมที่สุด: การฝังพื้นผิวทุกแบบของGต้องการจีนัสอย่างน้อย⁠τ/160อย่างไรก็ตามการหาจีนัสที่เหมาะสมที่สุดของการฝังพื้นผิวของกราฟยอดนั้นเป็นปัญหา NP-hard ^{[ 14 ]}

โดยการใช้ต้นไม้ SPQRเพื่อเข้ารหัสการฝังที่เป็นไปได้ของส่วนระนาบของกราฟยอด ทำให้สามารถคำนวณภาพวาดของกราฟในระนาบซึ่งมีเพียงจุดตัดที่เกี่ยวข้องกับจุดยอดเท่านั้น โดยลดจำนวนจุดตัดทั้งหมดให้น้อยที่สุดในเวลาพหุนาม^{[ 15 ]}อย่างไรก็ตาม หากอนุญาตให้มีจุดตัดตามอำเภอใจ การลดจำนวนจุดตัดให้น้อยที่สุดจะกลายเป็นปัญหา NP-hard แม้ในกรณีพิเศษของกราฟยอดที่เกิดจากการเพิ่มขอบเดียวให้กับกราฟระนาบ^{[ 16 ]}

กราฟเอเพ็กซ์ยังสามารถฝังตัวได้โดยไม่มีการเชื่อมโยงในพื้นที่สามมิติ : สามารถฝังตัวได้ในลักษณะที่แต่ละวงจรในกราฟเป็นขอบของดิสก์ที่ไม่ถูกตัดผ่านโดยคุณลักษณะอื่นใดของกราฟ^{[ 17 ]}การวาดภาพประเภทนี้สามารถทำได้โดยการวาดส่วนระนาบของกราฟในระนาบ วางเอเพ็กซ์ไว้เหนือระนาบ และเชื่อมต่อเอเพ็กซ์ด้วยขอบเส้นตรงกับเพื่อนบ้านแต่ละราย กราฟที่ฝังตัวได้โดยไม่มีการเชื่อมโยงก่อให้เกิดตระกูลปิดไมเนอร์โดยมีกราฟเจ็ดกราฟในตระกูลปีเตอร์เซนเป็นไมเนอร์ต้องห้ามขั้นต่ำ^{[ 1 ]}ดังนั้นกราฟเหล่านี้จึงถูกห้ามเป็นไมเนอร์สำหรับกราฟเอเพ็กซ์ด้วย อย่างไรก็ตาม มีกราฟที่ฝังตัวได้โดยไม่มีการเชื่อมโยงที่ไม่ใช่กราฟเอเพ็กซ์อยู่

กราฟที่เชื่อมต่อกันสามารถลดรูปได้เป็น YΔY หากสามารถลดรูปให้เหลือเพียงจุดยอดเดียวโดยลำดับขั้นตอน ซึ่งแต่ละขั้นตอนเป็นการแปลง Δ-Y หรือ Y-Δการลบวงวนตัวเองหรือการเชื่อมต่อหลายจุด การลบจุดยอดที่มีเพื่อนบ้านหนึ่งจุด และการแทนที่จุดยอดที่มีดีกรีสองและขอบที่อยู่ติดกันสองขอบด้วยขอบเดียว^{[ 3 ]}

เช่นเดียวกับกราฟเอเพ็กซ์และกราฟฝังตัวแบบไร้ลิงก์ กราฟ YΔY-reducible ปิดภายใต้กราฟไมเนอร์ และเช่นเดียวกับกราฟฝังตัวแบบไร้ลิงก์ กราฟ YΔY-reducible มีกราฟเจ็ดกราฟในตระกูล Petersenเป็นไมเนอร์ต้องห้าม ทำให้เกิดคำถามว่านี่เป็นเพียงไมเนอร์ต้องห้ามเท่านั้นหรือไม่ และกราฟ YΔY-reducible เหมือนกับกราฟฝังตัวแบบไร้ลิงก์หรือไม่ อย่างไรก็ตาม Neil Robertson ได้ยกตัวอย่างกราฟเอเพ็กซ์ที่ไม่ใช่ YΔY-reducible เนื่องจากกราฟเอเพ็กซ์ทุกกราฟสามารถฝังตัวแบบไร้ลิงก์ได้ นี่แสดงให้เห็นว่ามีกราฟที่สามารถฝังตัวแบบไร้ลิงก์ได้แต่ไม่ใช่ YΔY-reducible และดังนั้นจึงมีไมเนอร์ต้องห้ามเพิ่มเติมสำหรับกราฟ YΔY-reducible ^{[ 3 ]}

กราฟจุดยอดของโรเบิร์ตสันแสดงอยู่ในรูป สามารถสร้างได้โดยการเชื่อมต่อจุดยอดกับจุดยอดที่มีดีกรีสามของ ทรงสิบสองเหลี่ยม ขนมเปียกปูน หรือโดยการรวมจุดยอดสองจุดที่อยู่ตรงข้ามกันในแนวเส้นผ่านศูนย์กลางของ กราฟไฮเปอร์คิวบ์สี่มิติเนื่องจากกราฟของทรงสิบสองเหลี่ยมขนมเปียกปูนเป็นกราฟระนาบ กราฟของโรเบิร์ตสันจึงเป็นกราฟจุดยอด เป็นกราฟที่ไม่มีรูปสามเหลี่ยม และมี ดีกรีต่ำสุดสี่ ดังนั้นจึงไม่สามารถเปลี่ยนแปลงได้ด้วยการลดรูป YΔY ใดๆ^{[ 3 ]}

หากกราฟเป็นกราฟจุดยอด ก็ไม่ได้หมายความว่ามันจะมีจุดยอดเพียงจุดเดียวเสมอไป ตัวอย่างเช่น ในกราฟที่ไม่เป็นระนาบแบบมินิมอลK ₅และK _3,3จุดยอดใดๆ ก็สามารถเลือกเป็นจุดยอดได้ วากเนอร์ ( 1967 , 1970 ) นิยามกราฟเกือบเป็น ระนาบ ว่าเป็นกราฟจุดยอดที่ไม่เป็นระนาบที่มีคุณสมบัติว่าจุดยอดทุกจุดสามารถเป็นจุดยอดของกราฟได้ ดังนั้นK ₅และK _3,3จึงเป็นกราฟเกือบเป็นระนาบ เขาได้จำแนกกราฟเหล่านี้ออกเป็นสี่กลุ่มย่อย โดยกลุ่มหนึ่งประกอบด้วยกราฟที่ (เช่นบันไดโมเบียส ) สามารถฝังลงบนแถบโมเบียสได้ในลักษณะที่ขอบเดียวของแถบนั้นตรงกับวัฏจักรแฮมิลโทเนียนของกราฟ ก่อนที่จะพิสูจน์ทฤษฎีบทสี่สีเขาได้พิสูจน์ว่ากราฟเกือบระนาบทุกกราฟสามารถระบายสีได้ด้วยสีอย่างมากที่สุดสี่สี ยกเว้นกราฟที่เกิดจากกราฟวงล้อที่มีวงจรภายนอกเป็นเลขคี่ โดยการแทนที่จุดศูนย์กลางด้วยจุดยอดที่อยู่ติดกันสองจุด ซึ่งต้องใช้ห้าสี นอกจากนี้ เขายังพิสูจน์ได้ว่า ยกเว้นเพียงกรณีเดียว ( กราฟส่วนเติมเต็ม แปดจุดยอด ของลูกบาศก์ ) กราฟเกือบระนาบทุกกราฟสามารถฝังตัวลงบนระนาบเชิงโปรเจก ทีฟ ได้

อย่างไรก็ตาม วลี "กราฟเกือบระนาบ" นั้นมีความกำกวมสูง: มีการใช้เพื่ออ้างถึงกราฟยอด^{[ 18 ]}กราฟที่เกิดจากการเพิ่มขอบหนึ่งเส้นให้กับกราฟระนาบ^{[ 19 ]}และกราฟที่เกิดจากกราฟฝังตัวระนาบโดยการแทนที่หน้าจำนวนจำกัดด้วย "กระแสน้ำวน" ที่มีความกว้างเส้นทางจำกัด[ 20 ^{]รวมถึง}ชุดกราฟอื่นๆ ที่กำหนดได้ไม่แม่นยำนัก

กราฟนามธรรมเรียกว่ากราฟn -apex ถ้าสามารถทำให้เป็นกราฟระนาบได้โดยการลบ จุดยอด nจุดหรือน้อยกว่านั้น กราฟ 1-apex ก็เรียกว่ากราฟ apex เช่นกัน

ตามที่Lipton et al. (2018) กล่าวไว้ กราฟจะเป็นกราฟที่มีขอบเป็นจุดยอด (edge-apex)หากมีขอบบางขอบในกราฟที่สามารถลบออกได้เพื่อให้กราฟเป็นระนาบ และกราฟจะเป็นกราฟที่มีขอบเป็นจุดยอดแบบหดตัว (contraction-apex)หากมีขอบบางขอบในกราฟที่สามารถหดตัวได้เพื่อให้กราฟเป็นระนาบ

โดยทั่วไป ถ้าXเป็นกลุ่มของกราฟ กราฟ "apex- X " คือกราฟที่สามารถนำเข้ามาอยู่ในกลุ่มX ได้ โดยการลบจุดยอดบางจุดออกไป ตัวอย่างเช่น กราฟ apex- cographคือกราฟGที่มีจุดยอดvซึ่งทำให้G―vเป็นกราฟ cograph

• พีระมิดทรงหลายเหลี่ยมคือ รูปทรงหลายเหลี่ยม 4 มิติ ที่จุดยอดและขอบของพีระมิดประกอบกันเป็นกราฟยอด โดยที่ยอดนั้นอยู่ติดกับทุกจุดยอดของกราฟทรงหลายเหลี่ยม