ในทฤษฎีกราฟเชิงทอ พอโลยี การฝังตัว ( embedding ) ของกราฟบนพื้นผิวคือการแสดงกราฟบนพื้นผิวโดยที่จุดของกราฟจะเชื่อมโยงกับจุดยอดและส่วนโค้งแบบง่าย ( ภาพโฮโมมอร์ฟิก ของกราฟ ) จะเชื่อมโยงกับขอบในลักษณะที่ว่า: ${\displaystyle G}$${\displaystyle \Sigma }$${\displaystyle G}$${\displaystyle \Sigma }$${\displaystyle \Sigma }$${\displaystyle [0,1]}$

• จุดปลายของส่วนโค้งที่เชื่อมโยงกับขอบคือจุดที่เชื่อมโยงกับจุดยอดปลายของขอบนั้น${\displaystyle e}$${\displaystyle e,}$
• ส่วนโค้งใดๆ ก็ตามจะไม่รวมถึงจุดที่เชื่อมโยงกับจุดยอดอื่นๆ
• ส่วนโค้งสองส่วนจะไม่ตัดกัน ณ จุดที่อยู่ภายในส่วนโค้งใดส่วนโค้งหนึ่ง

ในที่นี้ พื้นผิวคือ แม นิโฟลด์ที่ เชื่อมต่อกัน${\displaystyle 2}$

โดยทั่วไป การฝังกราฟลงบนพื้นผิวคือการวาดกราฟลงบนพื้นผิวในลักษณะที่ขอบของกราฟจะตัดกันได้เฉพาะที่จุดปลายเท่านั้น เป็นที่ทราบกันดีว่ากราฟจำกัดใดๆ ก็สามารถฝังลงในพื้นที่ยูคลิด 3 มิติได้[ ^{1 ] กราฟ}ระนาบคือกราฟที่สามารถฝังลงในพื้นที่ยูคลิด 2 มิติได้${\displaystyle \mathbb {R} ^{3}}$${\displaystyle \mathbb {R} ^{2}.}$

โดยทั่วไปการฝังตัว (embedding) มัก ถูกมองว่าเป็นกลุ่มสมมูล (ภายใต้โฮมีโอเมอร์ฟิซึมของ) ของการแสดงแทนในลักษณะที่ได้อธิบายไปแล้ว ${\displaystyle \Sigma }$

ผู้เขียนบางคนกำหนดนิยามที่อ่อนกว่าของ "การฝังกราฟ" โดยละเว้นเงื่อนไขการไม่ตัดกันของขอบ ในบริบทดังกล่าว นิยามที่เข้มงวดกว่าจะถูกอธิบายว่าเป็น "การฝังกราฟที่ไม่ตัดกัน" ^{[ 2 ]}

บทความนี้กล่าวถึงเฉพาะนิยามที่เข้มงวดของการฝังกราฟเท่านั้น นิยามที่อ่อนกว่านั้นจะกล่าวถึงในบทความ " การวาดกราฟ " และ " จำนวนจุดตัด "

ถ้ากราฟถูกฝังอยู่บนพื้นผิวปิดส่วนเติมเต็มของการรวมกันของจุดและส่วนโค้งที่เกี่ยวข้องกับจุดยอดและขอบของกราฟจะเป็นตระกูลของภูมิภาค (หรือหน้า ) ^{[ 3 ]} การฝัง แบบ2 เซลล์การฝังแบบเซลลูลาร์หรือแผนที่คือการฝังที่ทุกหน้ามีลักษณะทางสัณฐานวิทยาเหมือนกับดิสก์เปิด^{[ 4 ]} การฝังแบบ 2 เซลล์ปิดคือการฝังที่การปิดของทุกหน้ามีลักษณะทางสัณฐานวิทยาเหมือนกับดิสก์ปิด ${\displaystyle G}$${\displaystyle \Sigma }$${\displaystyle G}$

เจนัสของกราฟคือจำนวนเต็มที่น้อยที่สุดที่ทำให้กราฟนั้นสามารถฝังลงบนพื้นผิวที่ มีเจ นัสเท่ากับ nได้ โดยเฉพาะอย่างยิ่งกราฟระนาบจะมีเจนัสเท่ากับ n เพราะสามารถวาดลงบนทรงกลมได้โดยไม่ตัดกันเอง กราฟที่สามารถฝังลงบนทอรัสได้เรียกว่ากราฟทอรัส ${\displaystyle n}$${\displaystyle n}$${\displaystyle 0}$

จีนัสที่ไม่สามารถกำหนดทิศทางได้ของกราฟคือจำนวนเต็มที่น้อยที่สุดที่กราฟสามารถฝังอยู่ในพื้นผิวที่ไม่สามารถกำหนดทิศทางได้ซึ่งมีจีนัส (ที่ไม่สามารถกำหนดทิศทางได้) ^{[ 3 ]}${\displaystyle n}$${\displaystyle n}$

เจนัสออยเลอร์ของกราฟ คือจำนวนเต็มที่น้อยที่สุดที่ทำให้กราฟนั้นสามารถฝังตัวอยู่ในพื้นผิวที่กำหนดทิศทางได้ (orientable surface) ที่มีเจนัส (orientable) หรือในพื้นผิวที่ไม่สามารถกำหนดทิศทางได้ (non-orientable surface) ที่มีเจนัส (non-orientable) กราฟจะเรียกว่ากราฟเชิงง่ายที่กำหนดทิศทางได้ (orientably simple)ถ้าเจนัสออยเลอร์ของกราฟนั้นน้อยกว่าเจนัสที่ไม่สามารถกำหนดทิศทางได้ของกราฟนั้น ${\displaystyle n}$${\displaystyle n/2}$${\displaystyle n}$

เจนัสสูงสุดของกราฟคือจำนวนเต็มที่มากที่สุดที่ทำให้กราฟนั้นสามารถฝังอยู่ในพื้นผิวที่กำหนดทิศทางได้ซึ่งมีเจนัสเท่ากับ nได้ ${\displaystyle n}$${\displaystyle 2}$${\displaystyle n}$

กราฟฝังตัวจะกำหนดลำดับวัฏจักรของขอบที่เชื่อมต่อกับจุดยอดเดียวกันอย่างเฉพาะเจาะจง เซตของลำดับวัฏจักรทั้งหมดเหล่านี้เรียกว่าระบบการหมุน การฝังตัวที่มีระบบการหมุนเดียวกันถือว่าเทียบเท่ากัน และชั้นความเทียบเท่าของการฝังตัวที่สอดคล้องกันเรียกว่าการฝังตัวเชิงคอมบินาทอริก (ตรงข้ามกับคำว่าการฝังตัวเชิงโทโพโลยีซึ่งหมายถึงคำจำกัดความก่อนหน้านี้ในแง่ของจุดและเส้นโค้ง) บางครั้ง ระบบการหมุนเองก็เรียกว่า "การฝังตัวเชิงคอมบินาทอริก" ^{[ 5 ] [ 6 ] [ 7 ]}

กราฟฝังตัวยังกำหนดลำดับวัฏจักรตามธรรมชาติของขอบ ซึ่งประกอบเป็นขอบเขตของหน้าของกราฟฝังตัว อย่างไรก็ตาม การจัดการลำดับตามหน้าเหล่านี้ทำได้ยากกว่า เนื่องจากในบางกรณี ขอบบางเส้นอาจถูกข้ามสองครั้งตามขอบเขตของหน้า ตัวอย่างเช่น กรณีนี้มักเกิดขึ้นเสมอสำหรับกราฟฝังตัวของต้นไม้ ซึ่งมีหน้าเดียว เพื่อเอาชนะความยุ่งยากเชิงการจัดเรียงนี้ เราอาจพิจารณาว่าขอบทุกเส้นถูก "แบ่ง" ตามความยาวออกเป็น "ขอบครึ่ง" หรือ "ด้าน" สองส่วน ภายใต้ข้อตกลงนี้ ในการข้ามขอบเขตของหน้าทั้งหมด ขอบครึ่งแต่ละส่วนจะถูกข้ามเพียงครั้งเดียว และขอบครึ่งทั้งสองของขอบเดียวกันจะถูกข้ามในทิศทางตรงกันข้ามเสมอ

รูปแบบการแสดงผลที่เทียบเท่ากันอื่นๆ สำหรับการฝังเซลล์ ได้แก่กราฟริบบอนซึ่งเป็นปริภูมิเชิงทอพอโลยีที่เกิดจากการเชื่อมต่อดิสก์เชิงทอพอโลยีสำหรับจุดยอดและขอบของกราฟที่ฝังอยู่ และแผนที่เข้ารหัสกราฟ ซึ่งเป็นกราฟลูกบาศก์ที่ระบายสีขอบโดยมีจุดยอดสี่จุดสำหรับแต่ละขอบของกราฟที่ฝังอยู่

ปัญหาของการค้นหาจีนัสของกราฟเป็นปัญหาNP-hard (ปัญหาของการพิจารณาว่ากราฟที่มีจุดยอด -จุดมีจีนัส หรือไม่ เป็นปัญหา NP-complete ) ^{[ 8 ]}${\displaystyle n}$${\displaystyle g}$

ในขณะเดียวกัน ปัญหาจีนัสของกราฟก็สามารถแก้ไขได้ด้วยพารามิเตอร์คงที่ กล่าว คือ มีอัลกอริธึม เวลาพหุนามที่ใช้ตรวจสอบว่ากราฟสามารถฝังลงในพื้นผิวที่มีจีนัสคงที่ที่กำหนดได้หรือไม่ รวมถึงการหาการฝังด้วย

ความก้าวหน้าครั้งแรกในเรื่องนี้เกิดขึ้นในปี 1979 เมื่ออัลกอริ ทึม ที่มีความซับซ้อนของเวลาO ( n ^{O ( g )} ) ถูกส่งไปที่การประชุมประจำปีของACM Symposium on Theory of Computing อย่างอิสระ โดยอั ลกอริทึมหนึ่งส่งโดย I. Filotti และGL Millerและอีกอัลกอริทึมหนึ่งส่งโดยJohn Reifแนวทางของพวกเขานั้นแตกต่างกันมาก แต่ตามคำแนะนำของคณะกรรมการโปรแกรม พวกเขาได้นำเสนอเอกสารร่วมกัน^{[ 9 ]}อย่างไรก็ตามWendy MyrvoldและWilliam Kocayได้พิสูจน์ในปี 2011 ว่าอัลกอริทึมที่ Filotti, Miller และ Reif นำเสนอนั้นไม่ถูกต้อง^{[ 10 ]}

ในปี พ.ศ. 2542 มีรายงานว่ากรณีที่มีจีนัสคงที่สามารถแก้ไขได้ในเวลาเชิงเส้นตามขนาดของกราฟและแบบเลขชี้กำลังสองเท่าตามจีนัส^{[ 11 ]}

เป็นที่ทราบกันว่ากราฟจำกัดใดๆ ก็สามารถฝังลงในปริภูมิสามมิติได้^{[ 1 ]}

วิธีหนึ่งในการทำเช่นนี้คือการวางจุดบนเส้นตรงใดๆ ในอวกาศ แล้ววาดเส้นขอบเป็นเส้นโค้ง โดยแต่ละเส้นโค้งจะอยู่บนระนาบครึ่ง ที่แตกต่างกัน โดยระนาบครึ่งทั้งหมดจะมีเส้นตรงนั้นเป็นขอบเขตร่วมกัน การฝังตัวแบบนี้ซึ่งวาดเส้นขอบบนระนาบครึ่งเรียกว่าการฝังตัวแบบหนังสือของกราฟคำอุปมา นี้ มาจากการจินตนาการว่าแต่ละระนาบที่วาดเส้นขอบนั้นเหมือนกับหน้าหนังสือ มีการสังเกตว่าในความเป็นจริงแล้วสามารถวาดเส้นขอบหลายเส้นใน "หน้า" เดียวกันได้ความหนาของหนังสือของกราฟคือจำนวนระนาบครึ่งขั้นต่ำที่จำเป็นสำหรับการวาดแบบนั้น

อีกทางเลือกหนึ่ง กราฟจำกัดใดๆ ก็สามารถวาดได้ด้วยเส้นขอบเส้นตรงในสามมิติโดยไม่มีจุดตัด โดยการวางจุดยอดในตำแหน่งทั่วไป เพื่อให้ไม่มีจุดยอดสี่จุดใดอยู่บนระนาบ เดียวกันตัวอย่างเช่น อาจทำได้โดยการวาง จุดยอดที่ iไว้ที่จุด ( i , i2 ^, i3 ⁾ของเส้นโค้งโมเมนต์

การฝังกราฟลงในพื้นที่สามมิติโดยที่ไม่มีวงจรสองวงใดเชื่อมโยงกันทางโทโพโลยี เรียกว่า การฝังแบบไร้การเชื่อมโยง (linkless embedding ) กราฟจะมีการฝังแบบไร้การเชื่อมโยงก็ต่อเมื่อกราฟนั้นไม่มีกราฟใดในเจ็ดกราฟของตระกูลปีเตอร์เซนเป็นกราฟย่อย (minor )

• 
  กราฟปีเตอร์เซนและแผนที่ที่เกี่ยวข้องซึ่งฝังอยู่ในระนาบเชิงฉาย จุดตรงข้ามบนวงกลมจะถูกระบุ ทำให้ได้พื้นผิวปิดที่มีจีนัส 1 ที่ไม่สามารถกำหนดทิศทางได้
• 
  กราฟPappusและแผนที่ที่เกี่ยวข้องซึ่งฝังอยู่ในทรงโดนัท
• 
  กราฟไคลน์ระดับ 7 และแผนที่ที่เกี่ยวข้องซึ่งฝังอยู่ในพื้นผิวที่กำหนดทิศทางได้ของจีนัส 3

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