ในทฤษฎีกราฟการฝังแบบหนังสือ (book embedding)คือการขยายแนวคิดของการฝังแบบระนาบ (planar embedding)ของกราฟไปสู่การฝังในหนังสือซึ่งเป็นชุดของระนาบครึ่งซีก ที่มี เส้นเดียวกันเป็นขอบเขต โดยปกติแล้ว จุดยอดของกราฟจะต้องอยู่บนขอบเขตนี้ ซึ่งเรียกว่าสันหนังสือ (spine ) และขอบจะต้องอยู่ภายในระนาบครึ่งซีกเดียวความหนาของหนังสือ (book thickness ) ของกราฟคือจำนวนระนาบครึ่งซีกที่น้อยที่สุดที่เป็นไปได้สำหรับการฝังแบบหนังสือใดๆ ของกราฟ ความหนาของหนังสือยังเรียกว่า หมายเลขหน้า ( pagenumber) หมายเลขกอง (stacknumber)หรือ ความหนาภายนอกคงที่ (fixed outerthickness ) การฝังแบบหนังสือยังถูกนำมาใช้เพื่อกำหนด ค่าคงที่อื่นๆ ของกราฟอีกหลายอย่างรวมถึงความกว้างของหน้า (pagewidth) และจำนวนจุดตัดของหนังสือ (book crossing number)

กราฟทุกกราฟที่มีnจุดยอดจะมีค่าความหนาหนังสือไม่เกินn และสูตรนี้ให้ค่าความหนาหนังสือที่แน่นอนสำหรับกราฟสมบูรณ์กราฟที่มีค่าความหนาหนังสือเท่ากับ 1 คือกราฟนอกระนาบกราฟที่มีค่าความหนาหนังสือไม่เกิน 2 คือกราฟย่อยแฮมิลโทเนียนซึ่งเป็น กราฟ ระนาบ เสมอ โดยทั่วไปแล้ว กราฟระนาบทุกกราฟจะมีค่าความหนาหนังสือไม่เกิน 4 การหาค่าความหนาหนังสือที่แน่นอนของกราฟที่กำหนดให้เป็น ปัญหา NP-hardไม่ว่าจะทราบหรือไม่ทราบลำดับจุดยอดคงที่ตามสันหนังสือก็ตาม การทดสอบการมีอยู่ของการฝังกราฟลงในหนังสือสามหน้า โดยกำหนดลำดับจุดยอดคงที่ตามสันของการฝัง มีความซับซ้อนในการคำนวณที่ไม่ทราบแน่ชัด กล่าวคือ ไม่ทราบว่าสามารถแก้ไขได้ในเวลาพหุนามหรือเป็นปัญหา NP-hard ${\displaystyle \lceil n/2\rceil }$

หนึ่งในแรงจูงใจดั้งเดิมในการศึกษาการฝังตัวแบบหนังสือเกี่ยวข้องกับการประยุกต์ใช้ใน การออกแบบ VLSIซึ่งจุดยอดของการฝังตัวแบบหนังสือแสดงถึงส่วนประกอบของวงจร และเส้นลวดแสดงถึงการเชื่อมต่อระหว่างส่วนประกอบเหล่านั้น การฝังตัวแบบหนังสือยังมีการประยุกต์ใช้ในการวาดกราฟ โดยรูปแบบการแสดงภาพกราฟมาตรฐานสองแบบ ได้แก่ แผนภาพส่วนโค้งและแผนภาพวงกลมสามารถสร้างได้โดยใช้การฝังตัวแบบหนังสือ

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

แนวคิดของหนังสือในฐานะพื้นที่เชิงทอพอโลยีได้รับการกำหนดโดย CA Persinger และ Gail Atneosen ในช่วงทศวรรษ 1960 ^{[ 1 ] [ 2 ]}ในส่วนหนึ่งของงานนี้ Atneosen ได้พิจารณาการฝังกราฟในหนังสือแล้ว การฝังที่เขาศึกษาใช้คำจำกัดความเดียวกันกับการฝังกราฟลงในพื้นที่เชิงทอพอโลยีอื่นๆ กล่าวคือ จุดยอดแทนด้วยจุดที่แตกต่างกัน ขอบแทนด้วยเส้นโค้ง และวิธีเดียวที่ขอบสองเส้นจะตัดกันได้คือต้องมาบรรจบกันที่จุดปลายร่วมกัน

ในช่วงต้นทศวรรษ 1970 Paul C. Kainenและ L. Taylor Ollmann ได้พัฒนารูปแบบการฝังตัวที่จำกัดมากขึ้น ซึ่งต่อมาได้ถูกนำมาใช้ในการวิจัยส่วนใหญ่ ในการกำหนดรูปแบบของพวกเขา จุดยอดของกราฟจะต้องวางอยู่ตามแนวสันหนังสือ และขอบแต่ละเส้นจะต้องอยู่ในหน้าเดียว^{[ 3 ] [ 4 ]} เหตุการณ์สำคัญในการพัฒนาการฝังตัวหนังสือในภายหลัง ได้แก่ การพิสูจน์โดยMihalis Yannakakisในช่วงปลายทศวรรษ 1980 ว่ากราฟระนาบมีความหนาหนังสือไม่เกินสี่^{[ 5 ] [ 6 ]} และการค้นพบความเชื่อมโยงอย่างใกล้ชิดระหว่างการฝังตัวหนังสือและ ชีวสารสนเทศในช่วงปลายทศวรรษ 1990 ^{[ 7 ]}

หนังสือ เป็น พื้นที่โทโพโลยีชนิดหนึ่งโดยเฉพาะ เรียกอีกอย่างว่าพัดของระนาบครึ่ง^{[ 1 ] [ 8 ]}ประกอบด้วยเส้นตรงเส้น เดียว ℓเรียกว่าสัน หนังสือ หรือด้านหลังของหนังสือ พร้อมด้วยชุดของระนาบครึ่ง หนึ่งหรือมากกว่า เรียกว่าหน้าหรือแผ่นของหนังสือ^{[ 9 ]}แต่ละหน้ามีสันหนังสือเป็นขอบเขต หนังสือที่มี จำนวน หน้าจำกัด สามารถ ฝังอยู่ในพื้นที่สามมิติได้ ตัวอย่างเช่น โดยการเลือกℓให้เป็น แกน zของระบบพิกัดคาร์ทีเซียนและเลือกหน้าให้เป็น^{ระนาบ} ครึ่ง kระนาบ ซึ่งมุมไดเฮดรัลเทียบกับ ระนาบ xzเป็นผลคูณจำนวนเต็มของ2 π / k ^{[ 10} ]

การวาดกราฟจำกัดG ลง บนหนังสือBเป็นการวาด G บนBโดยที่จุดยอดทุกจุดของGจะถูกวาดเป็นจุดบนสันหนังสือBและขอบทุกขอบของGจะถูกวาดเป็นเส้นโค้งที่อยู่ภายในหน้าเดียวของBจำนวนการข้ามหนังสือkหน้าของGคือจำนวนการข้าม ขั้นต่ำ ใน การวาดหนังสือ kหน้า^{[ 11 ]}

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

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

ดังแสดงในรูปแรก ความหนาของหนังสือของกราฟสมบูรณ์K ₅คือสาม: เนื่องจากเป็นกราฟที่ไม่ใช่ระนาบ ความหนาของหนังสือจึงมากกว่าสอง แต่มีการฝังหนังสือที่มีสามหน้า โดยทั่วไปแล้ว ความหนาของหนังสือของกราฟสมบูรณ์ทุกกราฟที่มีn ≥ 4จุดยอดคือผลลัพธ์นี้ยังให้ขอบเขตบนของความหนาของหนังสือสูงสุดที่เป็นไปได้ของกราฟn จุดยอดใดๆ อีกด้วย ^{[ 10 ]}${\displaystyle \lceil n/2\rceil }$

จำนวนจุดตัดสองหน้าของกราฟสมบูรณ์K _nคือ

${\displaystyle {\frac {1}{4}}{\biggl \lfloor }{\frac {n}{2}}{\biggr \rfloor }{\biggl \lfloor }{\frac {n-1}{2}}{\biggr \rfloor }{\biggl \lfloor }{\frac {n-2}{2}}{\biggr \rfloor }{\biggl \lfloor }{\frac {n-3}{2}}{\biggr \rfloor },}$

ตรงกับสมมติฐานที่ยังไม่ได้รับการพิสูจน์ของแอนโทนี ฮิลล์เกี่ยวกับจำนวนจุดตัดที่ไม่จำกัดของกราฟนี้ กล่าวคือ หากสมมติฐานของฮิลล์ถูกต้อง การวาดกราฟนี้ที่ลดจำนวนจุดตัดให้น้อยที่สุดจะเป็นภาพวาดสองหน้า^{[ 18 ]}

ความหนาของหนังสือของกราฟสองส่วนสมบูรณ์K _{a , b}มีค่าไม่เกินmin( a , b )ในการสร้างภาพวาดที่มีความหนาของหนังสือนี้ สำหรับแต่ละจุดยอดบนด้านที่เล็กกว่าของการแบ่งสองส่วน เราสามารถวางขอบที่เชื่อมต่อกับจุดยอดนั้นบนหน้าของตัวเองได้ ขอบเขตนี้ไม่แน่นเสมอไป ตัวอย่างเช่นK _4,4มีความหนาของหนังสือสาม ไม่ใช่สี่ อย่างไรก็ตาม เมื่อสองด้านของกราฟไม่สมดุลกันมาก โดยที่b > a ( a − 1)ความหนาของหนังสือของK _{a , b}จะมีค่าเท่ากับaพอดี^{[ 10 ] [ 19 ]}

สำหรับกราฟ Turán T ( kr , r ) ( กราฟหลายส่วนสมบูรณ์K _{k , k ,...}ที่สร้างขึ้นจากเซตอิสระr เซต โดยแต่ละเซตอิสระ มี จุดยอด kจุด และมีขอบเชื่อมระหว่างจุดยอดสองจุดจากเซตอิสระที่แตกต่างกัน) ความหนาของหนังสือtจะอยู่ระหว่าง

${\displaystyle \left\lceil {\frac {k(r-1)}{2}}\right\rceil \leq t\leq \left\lceil {\frac {kr}{2}}\right\rceil }$

และเมื่อrเป็นจำนวนคี่ ขอบเขตบนสามารถปรับปรุงให้ดีขึ้นได้เป็น

${\displaystyle t\leq (r-1)\left\lceil {\frac {k}{2}}\right\rceil +\left\lceil {\frac {k}{4}}\right\rceil .}$^{[ 10 ] [ 20 ]}

ความหนาของหนังสือของ กราฟไบนารีเดอบรูอินกราฟสลับแลกเปลี่ยนและวงจรเชื่อมต่อลูกบาศก์ (เมื่อกราฟเหล่านี้มีขนาดใหญ่พอที่จะไม่เป็นระนาบ) คือสามพอดี^{[ 21 ]}

ความหนาของหนังสือสำหรับกราฟGจะมีค่าอย่างมากที่สุดหนึ่งก็ต่อเมื่อGเป็นกราฟแบบระนาบนอก (outerplanar graph) กราฟแบบระนาบนอกคือกราฟที่มีการฝังตัวในระนาบซึ่งจุดยอดทั้งหมดอยู่บนระนาบด้านนอกของการฝังตัว สำหรับกราฟดังกล่าว การวางจุดยอดในลำดับเดียวกันตามสันหนังสือเช่นเดียวกับที่ปรากฏบนระนาบด้านนอกจะทำให้ได้การฝังตัวในหนังสือหนึ่งหน้าสำหรับกราฟที่กำหนด ( จุดเชื่อมต่อของกราฟจะปรากฏมากกว่าหนึ่งครั้งในลำดับการเรียงตัวแบบวนรอบของจุดยอดรอบระนาบด้านนอก แต่จะมีเพียงสำเนาเดียวเท่านั้นที่จะถูกรวมอยู่ในการฝังตัวในหนังสือ) ในทางกลับกัน การฝังตัวในหนังสือหนึ่งหน้าจะเป็นการฝังตัวแบบระนาบนอกโดยอัตโนมัติ เพราะหากกราฟถูกฝังตัวบนหน้าเดียว และมีการเพิ่มระนาบครึ่งหนึ่งเข้ากับสันหนังสือเพื่อขยายหน้าให้เป็นระนาบที่สมบูรณ์ ระนาบด้านนอกของการฝังตัวจะรวมระนาบครึ่งหนึ่งที่เพิ่มเข้ามาทั้งหมด และจุดยอดทั้งหมดจะอยู่บนระนาบด้านนอกนี้^{[ 10 ] [ 12 ]}

การฝังหนังสือสองหน้าทุกกรณีเป็นกรณีพิเศษของการฝังแบบระนาบ เนื่องจากการรวมกันของสองหน้าของหนังสือเป็นพื้นที่ที่เทียบเท่าทางโทโพโลยีกับระนาบทั้งหมด ดังนั้นกราฟทุกกราฟที่มีความหนาหนังสือสองจึงเป็นกราฟระนาบโดยอัตโนมัติ กล่าวคือ ความหนาหนังสือของกราฟGจะมีค่าไม่เกินสองก็ต่อเมื่อGเป็นกราฟย่อยของกราฟระนาบที่มีวัฏจักรแฮมิลโทเนียน^{[ 10 ]}หากกราฟได้รับการฝังสองหน้า กราฟนั้นสามารถเสริมให้เป็นกราฟแฮมิลโทเนียนระนาบได้โดยการเพิ่ม (ในหน้าใดก็ได้) ขอบพิเศษระหว่างจุดยอดสองจุดที่อยู่ติดกันตามสันหนังสือที่ยังไม่ได้อยู่ติดกัน และระหว่างจุดยอดสันหนังสือแรกและจุดยอดสันหนังสือสุดท้ายกราฟ Goldner–Hararyเป็นตัวอย่างของกราฟระนาบที่ไม่มีความหนาหนังสือสอง: มันเป็นกราฟระนาบสูงสุดดังนั้นจึงไม่สามารถเพิ่มขอบใดๆ ลงไปได้ในขณะที่ยังคงรักษาความเป็นระนาบไว้ และไม่มีวัฏจักรแฮมิลโทเนียน^{[ 10 ]}เนื่องจากการกำหนดลักษณะโดยวงจรแฮมิลโทเนียน กราฟที่มีการฝังหนังสือสองหน้าจึงเรียกว่ากราฟซับแฮมิลโทเนียน^{[ 12 ]}

กราฟระนาบทั้งหมดที่มีดีกรีสูงสุดไม่เกินสี่จะมีความหนาของหนังสือไม่เกินสอง^{[ 22 ]}ต้นไม้ 3 มิติแบบระนาบจะมีความหนาของหนังสือไม่เกินสาม^{[ 23 ]}โดยทั่วไปแล้ว กราฟระนาบทั้งหมดจะมีความหนาของหนังสือสี่^{[ 5 ] [ 6 ] [ 24 ]} Mihalis Yannakakisได้กล่าวอ้างในปี 1986 ^{[ 6 ]}ว่ามีกราฟระนาบบางประเภทที่มีความหนาของหนังสือเท่ากับสี่พอดี อย่างไรก็ตาม การพิสูจน์อย่างละเอียดของข้ออ้างนี้ ซึ่งประกาศในวารสารฉบับต่อมา^{[ 5 ]}ยังไม่เป็นที่รู้จักจนกระทั่งปี 2020 เมื่อ Bekos et al. ^{[ 24 ]}นำเสนอกราฟระนาบที่มีความกว้างของต้นไม้ เท่ากับ 4 ซึ่งต้องใช้สี่หน้าในการฝังหนังสือใดๆ

การแบ่งขอบแต่ละขอบของกราฟออกเป็นเส้นทางสองขอบ โดยการเพิ่มจุดยอดใหม่ภายในแต่ละขอบ อาจทำให้ความหนาของหนังสือเพิ่มขึ้นได้ ตัวอย่างเช่นกราฟรูปเพชรมีความหนาของหนังสือเท่ากับหนึ่ง (เป็นกราฟระนาบนอก) แต่การแบ่งย่อยของกราฟนี้มีความหนาของหนังสือเท่ากับสอง (เป็นกราฟระนาบและกราฟซับแฮมิลโทเนียน แต่ไม่ใช่กราฟระนาบนอก) อย่างไรก็ตาม กระบวนการแบ่งย่อยนี้บางครั้งก็สามารถลดความหนาของหนังสือของกราฟที่แบ่งย่อยลงได้อย่างมาก ตัวอย่างเช่น ความหนาของหนังสือของกราฟสมบูรณ์K _nเป็นสัดส่วนกับจำนวนจุดยอด แต่การแบ่งขอบแต่ละขอบออกเป็นเส้นทางสองขอบจะทำให้ได้กราฟที่แบ่งย่อยซึ่งมีความหนาของหนังสือน้อยกว่ามาก เพียง[ ^{25 ] แม้}จะมีตัวอย่างเช่นนี้Blankenship & Oporowski (1999) ก็ตั้งข้อสันนิษฐานว่าความหนาของหนังสือของกราฟที่แบ่งย่อยนั้นไม่ควรน้อยกว่าความหนาของหนังสือของกราฟเดิมมากนัก โดยเฉพาะอย่างยิ่ง พวกเขาตั้งสมมติฐานว่ามีฟังก์ชันf อยู่ ซึ่งสำหรับกราฟG ทุกกราฟ และสำหรับกราฟHที่เกิดจากการแทนที่ขอบทุกขอบในGด้วยเส้นทางสองขอบ หากความหนาของหนังสือของHคือtแล้วความหนาของหนังสือของGจะมีค่าไม่เกินf ( t ) ^{[ 16 ]}สมมติฐานของพวกเขากลับกลายเป็นเท็จ: กราฟที่เกิดจากผลคูณคาร์ทีเซียนของดาวและการปูพื้นแบบสามเหลี่ยม มีความหนาของหนังสือไม่จำกัด แต่ การแบ่งขอบของกราฟออกเป็นเส้นทางหกขอบจะลดความหนาของหนังสือลงเหลือสาม^{[ 26 ]}${\displaystyle O({\sqrt {n}})}$

ความหนาของหนังสือเกี่ยวข้องกับความหนาซึ่งเป็นจำนวนกราฟระนาบที่จำเป็นในการครอบคลุมขอบของกราฟที่กำหนด กราฟGมีความหนาθถ้าสามารถวาดลงบนระนาบได้ และขอบของกราฟถูกระบายสีด้วย สี θสี โดยที่ขอบที่มีสีเดียวกันจะไม่ตัดกัน ในทำนองเดียวกัน กราฟGมีความหนาของหนังสือθถ้าสามารถวาดลงบนระนาบครึ่ง ได้ โดยมีจุดยอดอยู่บนขอบของระนาบครึ่งนั้น และมีขอบถูกระบายสีด้วย สี θสี โดยไม่มีการตัดกันระหว่างขอบสองเส้นที่มีสีเดียวกัน ในการกำหนดความหนาของหนังสือนี้ สีของขอบจะสอดคล้องกับหน้าของหนังสือที่ฝังตัวอยู่ อย่างไรก็ตาม ความหนาและความหนาของหนังสืออาจแตกต่างกันมาก มีกราฟ ( การแบ่งย่อยของกราฟสมบูรณ์ ) ที่มีความหนาของหนังสือไม่จำกัด^{[ 25 ] [ 15 ] [ 16 ]}แม้ว่าจะมีความหนาเป็นสองก็ตาม^{[ 25 ]}

กราฟที่มีtreewidth kมีความหนาของหนังสือไม่เกินk + 1 ^{[ 27 ] [ 28 ]}และขอบเขตนี้แน่นสำหรับ k > 2 [ ^{27 ] กราฟ}ที่มี ขอบ mมีความหนาของหนังสือ[ ^{29 ] และ}กราฟที่มีจีนัสgมีความหนาของหนังสือ[ ^{30 ] โดย}ทั่วไปแล้ว มีการกล่าวว่ากราฟตระกูลที่ปิดภายใต้ minor ทุกตระกูล มีความหนาของหนังสือที่จำกัด^{[ 31 ] [ 32 ]}อย่างไรก็ตาม การพิสูจน์ข้ออ้างนี้ขึ้นอยู่กับข้ออ้างก่อนหน้านี้ที่ว่ากราฟที่ฝังอยู่บนพื้นผิวที่ไม่สามารถกำหนดทิศทางได้มีความหนาของหนังสือที่จำกัด ซึ่งยังไม่มีการพิสูจน์โดยละเอียด^{[ 33 ]}กราฟระนาบ 1ซึ่งไม่ปิดภายใต้ minor ^{[ 31 ]}มีความหนาของหนังสือที่จำกัด^{[ 34 ]}แต่กราฟระนาบ 1 บางกราฟรวมถึงK _2,2,2,2มีความหนาของหนังสืออย่างน้อยสี่^{[ 35 ]}${\displaystyle O({\sqrt {m}})}$${\displaystyle O({\sqrt {g}})}$

ไมเนอร์ตื้นทุก ตัว ของกราฟที่มีความหนาของหนังสือจำกัดจะเป็นกราฟเบาบางซึ่งอัตราส่วนของขอบต่อจุดยอดจะถูกจำกัดด้วยค่าคงที่ที่ขึ้นอยู่กับความลึกของไมเนอร์และความหนาของหนังสือเท่านั้น กล่าวคือ ในศัพท์เฉพาะของNešetřil & Ossona de Mendez (2012)กราฟที่มีความหนาของหนังสือจำกัดจะมีการขยายตัวที่จำกัด [ ^{31 ]}อย่างไรก็ตาม แม้แต่กราฟที่มีดีกรี จำกัด ซึ่งเป็นข้อกำหนดที่เข้มงวดกว่าการมีการขยายตัวที่จำกัด ก็อาจมีความหนาของหนังสือไม่จำกัด^{ได้[ 36 ]}

เนื่องจากกราฟที่มีความหนาของหนังสือเท่ากับสองเป็นกราฟระนาบ จึงเป็นไปตามทฤษฎีบทตัวคั่นระนาบ กล่าวคือ กราฟเหล่านี้มีตัวคั่น ซึ่งเป็นเซตย่อยของจุดยอดที่การลบออกจะแบ่งกราฟออกเป็นชิ้น ๆ โดยแต่ละชิ้นมีจุดยอดไม่เกิน2 n /3จุด โดยมีเฉพาะจุดยอดในตัวคั่นเท่านั้น ในที่นี้nหมายถึงจำนวนจุดยอดในกราฟ อย่างไรก็ตาม มีกราฟที่มีความหนาของหนังสือเท่ากับสามที่ไม่มีตัวคั่นที่มีขนาดต่ำกว่าเชิงเส้น^{[ 37 ]}${\displaystyle O({\sqrt {n}})}$

ขอบภายในหน้าเดียวของการฝังข้อมูลแบบหนังสือมีพฤติกรรมบางอย่างคล้ายกับโครงสร้างข้อมูลแบบสแต็กสามารถอธิบายได้โดยการพิจารณาลำดับการดำเนินการ push และ pop ใดๆ บนสแต็ก และสร้างกราฟที่การดำเนินการบนสแต็กสอดคล้องกับจุดยอดของกราฟ ซึ่งวางเรียงตามลำดับบนสันของหน้าเดียวของการฝังข้อมูลแบบหนังสือ จากนั้น หากลากขอบจากการดำเนินการ pop แต่ละครั้งที่ดึงวัตถุx ออก จากสแต็ก ไปยังการดำเนินการ push ก่อนหน้าที่เพิ่มxเข้าไป กราฟที่ได้จะมีหน้าเดียวโดยอัตโนมัติ ด้วยเหตุนี้ หมายเลขหน้าของกราฟจึงถูกเรียกว่าหมายเลขสแต็ก ด้วย เช่นกัน ในทำนองเดียวกัน เราอาจพิจารณาลำดับการดำเนินการ enqueue และ dequeue ใดๆ ของโครงสร้างข้อมูลแบบคิวและสร้างกราฟที่มีการดำเนินการเหล่านี้เป็นจุดยอด ซึ่งวางเรียงตามลำดับบนสันของหน้าเดียว โดยมีขอบระหว่างการดำเนินการ enqueue แต่ละครั้งกับการดำเนินการ dequeue ที่สอดคล้องกัน จากนั้น ในกราฟนี้ ขอบสองเส้นแต่ละคู่จะตัดกันหรือครอบคลุมช่วงเวลาที่ไม่ทับซ้อนกันบนสันหนังสือ โดยการเปรียบเทียบ นักวิจัยได้กำหนดการฝังคิวของกราฟให้เป็นการฝังในหนังสือเชิงโทโพโลยี โดยที่จุดยอดแต่ละจุดอยู่บนสันหนังสือ ขอบแต่ละเส้นอยู่บนหน้าเดียว และขอบสองเส้นแต่ละคู่ในหน้าเดียวกันจะตัดกันหรือครอบคลุมช่วงเวลาที่ไม่ทับซ้อนกันบนสันหนังสือ จำนวนหน้าขั้นต่ำที่จำเป็นสำหรับการฝังคิวของกราฟเรียกว่าหมายเลขคิว^{[ 31 ] [ 38 ] [ 39 ]}

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

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

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

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

Bekos, Kaufmann & Zielke (2015)อธิบายระบบสำหรับการค้นหาการฝังหนังสือที่เหมาะสมที่สุดโดยการแปลงปัญหาให้เป็นอินสแตนซ์ของปัญหาความพึงพอใจแบบบูลีนและใช้ตัวแก้ปัญหา SAT กับปัญหาที่ได้ พวกเขาระบุว่าระบบของพวกเขาสามารถค้นหาการฝังที่เหมาะสมที่สุดสำหรับกราฟระนาบสูงสุด 400 จุดยอดได้ ในเวลาประมาณ 20 นาที^{[ 35 ]}

หนึ่งในแรงจูงใจหลักในการศึกษาการฝังตัวแบบหนังสือที่กล่าวถึงโดยChung, Leighton & Rosenberg (1987)เกี่ยวข้องกับการประยุกต์ใช้ใน การออกแบบ VLSIในการจัดระเบียบมัลติโปรเซสเซอร์ที่ทนต่อความผิดพลาด ในระบบ DIOGENES ที่พัฒนาโดยผู้เขียนเหล่านี้CPUของระบบมัลติโปรเซสเซอร์จะถูกจัดเรียงเป็นลำดับตรรกะที่สอดคล้องกับสันหนังสือ (แม้ว่าลำดับนี้อาจไม่ได้วางเรียงตามแนวเส้นตรงในโครงสร้างทางกายภาพของระบบนี้ก็ตาม) ลิงก์การสื่อสารที่เชื่อมต่อโปรเซสเซอร์เหล่านี้จะถูกจัดกลุ่มเป็น "บันเดิล" ซึ่งสอดคล้องกับหน้าหนังสือและทำหน้าที่เหมือนกองซ้อน : การเชื่อมต่อโปรเซสเซอร์ตัวหนึ่งเข้ากับจุดเริ่มต้นของลิงก์การสื่อสารใหม่จะผลักลิงก์ก่อนหน้าทั้งหมดขึ้นไปในบันเดิล และการเชื่อมต่อโปรเซสเซอร์อีกตัวหนึ่งเข้ากับจุดสิ้นสุดของลิงก์การสื่อสารจะเชื่อมต่อกับตัวที่อยู่ด้านล่างสุดของบันเดิลและดึงลิงก์อื่นๆ ทั้งหมดลงมา เนื่องจากพฤติกรรมแบบกองซ้อนนี้ บันเดิลเดียวจึงสามารถจัดการชุดของลิงก์การสื่อสารที่ประกอบเป็นขอบของหน้าเดียวในการฝังตัวแบบหนังสือได้ ด้วยการจัดระเบียบลิงก์ในลักษณะนี้ สามารถนำโทโพโลยีเครือข่ายที่แตกต่างกันได้หลากหลายมาใช้ ไม่ว่าโปรเซสเซอร์ตัวใดจะเกิดความผิดพลาด ตราบใดที่ยังมีโปรเซสเซอร์ที่ไม่ผิดพลาดเหลืออยู่เพียงพอที่จะนำโทโพโลยีเครือข่ายมาใช้ โทโพโลยีเครือข่ายที่สามารถนำมาใช้โดยระบบนี้คือโทโพโลยีที่มีความหนาของหนังสือไม่เกินจำนวนมัดที่มีอยู่^{[ 41 ]} การฝังหนังสือยังสามารถใช้เพื่อจำลองการวางสายไฟที่เชื่อมต่อส่วนประกอบ VLSI เข้ากับเลเยอร์ของวงจรได้อีกด้วย^{[ 51 ]}

แอปพลิเคชันอื่นที่Chung, Leighton & Rosenberg (1987)อ้างถึงเกี่ยวข้องกับการเรียงลำดับการ เรียงสับเปลี่ยน โดยใช้สแต็กผลลัพธ์ที่มีอิทธิพลของDonald Knuth  ( 1968 ) แสดงให้เห็นว่าระบบที่ประมวลผลสตรีมข้อมูลโดยการผลักองค์ประกอบที่เข้ามาลงในสแต็ก จากนั้นในเวลาที่เลือกอย่างเหมาะสม จะดึงองค์ประกอบเหล่านั้นออกจากสแต็กไปยังสตรีมเอาต์พุต สามารถเรียงลำดับข้อมูลได้ก็ต่อเมื่อลำดับเริ่มต้นของข้อมูลนั้นอธิบายได้ด้วยการเรียงสับเปลี่ยนที่หลีกเลี่ยงรูปแบบการเรียงสับเปลี่ยน 231 ^{[ 52 ]}ตั้งแต่นั้นมา มีงานวิจัยมากมายเกี่ยวกับปัญหาที่คล้ายกันของการเรียงลำดับสตรีมข้อมูลโดยใช้ระบบสแต็กและคิวทั่วไปมากขึ้น ในระบบที่Chung, Leighton & Rosenberg (1987) พิจารณา องค์ประกอบแต่ละรายการจากสตรีมข้อมูลขาเข้าจะต้องถูกผลักลงในสแต็กหนึ่งในหลายๆ สแต็ก จากนั้นเมื่อข้อมูลทั้งหมดถูกผลักในลักษณะนี้แล้ว รายการต่างๆ จะถูกดึงออกจากสแต็กเหล่านี้ (ตามลำดับที่เหมาะสม) ไปยังสตรีมเอาต์พุต ดังที่ Chung et al. สังเกตได้ว่า การเรียงสับเปลี่ยนที่กำหนดสามารถเรียงลำดับโดยระบบนี้ได้ก็ต่อเมื่อกราฟที่กำหนดซึ่งได้มาจากการเรียงสับเปลี่ยนมีการฝังหนังสือโดยมีจุดยอดอยู่ในลำดับคงที่ตามสันหนังสือและมีจำนวนหน้าไม่เกินจำนวนกอง^{[ 41 ]}

ตามที่Kainen (1990)อธิบายไว้ การฝังข้อมูลลงในหนังสืออาจใช้เพื่ออธิบายขั้นตอนของสัญญาณไฟจราจรณ สี่แยกที่มีการควบคุม ณ สี่แยกนั้น เลนจราจรขาเข้าและขาออก (รวมถึงปลายทางข้ามทางเท้าและเลนจักรยาน ตลอดจนเลนสำหรับรถยนต์) อาจแสดงเป็นจุดยอดของกราฟ ซึ่งวางอยู่บนสันหนังสือโดยเรียงตามเข็มนาฬิการอบสี่แยก เส้นทางที่รถใช้ผ่านสี่แยกเพื่อไปยังเลนขาออกอาจแสดงเป็นขอบของกราฟแบบไม่มีทิศทาง ตัวอย่างเช่น กราฟนี้อาจมีขอบจากเลนขาเข้าไปยังเลนขาออกที่ทั้งสองเลนอยู่ในส่วนของถนนเดียวกัน ซึ่งแสดงถึงการกลับรถจากส่วนนั้นกลับไปยังส่วนนั้นอีกครั้ง เฉพาะในกรณีที่อนุญาตให้กลับรถได้ที่สี่แยกนั้น สำหรับเซตย่อยของขอบเหล่านี้ เซตย่อยจะแสดงถึงชุดของเส้นทางที่สามารถเดินทางผ่านได้โดยไม่มีการรบกวนซึ่งกันและกันก็ต่อเมื่อเซตย่อยนั้นไม่รวมขอบคู่ใด ๆ ที่จะตัดกันหากขอบทั้งสองถูกวางไว้ในหน้าเดียวของการฝังหนังสือ ดังนั้น การฝังหนังสือของกราฟนี้จึงอธิบายการแบ่งเส้นทางออกเป็นเซตย่อยที่ไม่รบกวนกัน และความหนาของหนังสือของกราฟนี้ (โดยมีการฝังคงที่บนสันหนังสือ) จะให้จำนวนเฟสที่แตกต่างกันขั้นต่ำที่จำเป็นสำหรับตารางสัญญาณที่รวมเส้นทางจราจรที่เป็นไปได้ทั้งหมดผ่านทางแยก^{[ 53 ]}

การฝังหนังสือยังถูกนำมาใช้บ่อยครั้งในการแสดงภาพข้อมูลเครือข่าย รูปแบบมาตรฐานสองแบบในการวาดกราฟได้แก่ แผนภาพส่วนโค้ง^{[ 54 ]}และรูปแบบวงกลม^{[ 55 ]}สามารถมองได้ว่าเป็นการฝังหนังสือ และการฝังหนังสือยังถูกนำมาใช้ในการสร้างรูปแบบคลัสเตอร์^{[ 46 ]}การฝังพร้อมกัน^{[ 56 ]}และการวาดกราฟสามมิติ^{[ 57 ]}

แผนภาพส่วนโค้ง^{[ 54 ]}หรือการฝังเชิงเส้น^{[ 44 ]}จะวางจุดยอดของกราฟตามแนวเส้นตรง และวาดขอบของกราฟเป็นครึ่งวงกลมทั้งด้านบนหรือด้านล่างของเส้นตรงนี้ บางครั้งยังอนุญาตให้วาดขอบบนส่วนต่างๆ ของเส้นตรงได้ด้วย รูปแบบการวาดนี้สอดคล้องกับการฝังแบบหนังสือที่มีหนึ่งหน้า (ถ้าครึ่งวงกลมทั้งหมดอยู่เหนือเส้นตรง) หรือสองหน้า (ถ้าใช้ทั้งสองด้านของเส้นตรง) และเดิมทีถูกนำมาใช้เป็นวิธีการศึกษาจำนวนจุดตัดของกราฟ^{[ 58 ] [ 59 ]}กราฟระนาบที่ไม่มีการฝังแบบหนังสือสองหน้าอาจวาดในลักษณะเดียวกันได้ โดยอนุญาตให้แสดงขอบด้วยครึ่งวงกลมหลายอันทั้งด้านบนและด้านล่างของเส้นตรง การวาดแบบนี้ไม่ใช่การฝังแบบหนังสือตามคำจำกัดความปกติ แต่เรียกว่าการฝังแบบหนังสือเชิงโทโพโลยี^{[ 60 ]}สำหรับกราฟระนาบทุกกราฟ จะสามารถหาการฝังตัวได้เสมอ โดยที่ขอบแต่ละเส้นจะตัดกับแกนหลักได้ไม่เกินหนึ่งครั้ง^{[ 61 ]}

ในรูปแบบการวาดอีกแบบหนึ่งคือการจัดวางแบบวงกลมโดยวางจุดยอดของกราฟไว้บนวงกลม และวาดเส้นขอบไว้ด้านในหรือด้านนอกวงกลม^{[ 55 ]}อีกครั้ง การวางเส้นขอบไว้ด้านในวงกลม (เช่น ส่วนของเส้นตรง) จะสอดคล้องกับภาพวาดหนังสือหนึ่งหน้า ในขณะที่การวางเส้นขอบไว้ทั้งด้านในและด้านนอกวงกลมจะสอดคล้องกับภาพวาดหนังสือสองหน้า^{[ 62 ]}

สำหรับการวาดภาพหน้าเดียวไม่ว่าจะเป็นสไตล์ใดก็ตาม สิ่งสำคัญคือต้องรักษาจำนวนจุดตัดให้น้อยที่สุดเพื่อลดความรกตาของภาพวาด การลดจำนวนจุดตัดให้น้อยที่สุดเป็นปัญหาNP-complete [ ^{44 ] แต่}สามารถประมาณได้ด้วยอัตราส่วนการประมาณO (log ²ⁿ  )โดยที่nคือจำนวนจุดยอด^{[ 63 ]}การลดจำนวนจุดตัดในหนึ่งหน้าหรือสองหน้าให้น้อยที่สุดนั้น สามารถ แก้ไขได้ด้วยพารามิเตอร์คงที่เมื่อกำหนดพารามิเตอร์ด้วยจำนวนไซโคลมาติกของกราฟที่กำหนด หรือด้วยการรวมกันของจำนวนจุดตัดและความกว้างของต้นไม้ของกราฟ^{[ 64 ] [ 65 ]}นอกจากนี้ยังมีการคิดค้นวิธีการฮิวริสติกเพื่อลดความซับซ้อนของจุดตัด โดยอิงจากลำดับการแทรกจุดยอดอย่างระมัดระวังและ การเพิ่มประสิทธิภาพ เฉพาะที่^{[ 55 ]}

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

การฝังหนังสือที่มีมากกว่าสองหน้ายังถูกนำมาใช้เพื่อสร้างภาพวาดสามมิติของกราฟ โดยเฉพาะอย่างยิ่งWood (2002)ได้ใช้การสร้างสำหรับการฝังหนังสือที่รักษาระดับของแต่ละจุดยอดภายในแต่ละหน้าให้ต่ำ ซึ่งเป็นส่วนหนึ่งของวิธีการฝังกราฟลงในตารางสามมิติที่มีปริมาตรต่ำ^{[ 57 ]}

ในการศึกษาเกี่ยวกับการ พับตัวของโมเลกุล RNAเพื่อสร้างโครงสร้างนั้น รูปแบบมาตรฐานของโครงสร้างทุติยภูมิของกรดนิวคลีอิกสามารถอธิบายได้ด้วยแผนภาพเป็นสายโซ่ของเบส (ลำดับ RNA เอง) ที่ลากไปตามเส้นตรง พร้อมกับส่วนโค้งหลายส่วนที่อยู่เหนือเส้นตรงนั้น ซึ่งอธิบายถึงคู่เบสของโครงสร้าง กล่าวคือ แม้ว่าโครงสร้างเหล่านี้จะมีรูปร่างสามมิติที่ซับซ้อน แต่การเชื่อมต่อของพวกมัน (เมื่อมีโครงสร้างทุติยภูมิอยู่) สามารถอธิบายได้ด้วยโครงสร้างที่เป็นนามธรรมมากกว่า นั่นคือ การฝังตัวในหนังสือหนึ่งหน้า อย่างไรก็ตาม การพับตัวของ RNA ทั้งหมดไม่ได้มีพฤติกรรมที่เรียบง่ายเช่นนี้เสมอไปHaslinger & Stadler (1999)ได้เสนอสิ่งที่เรียกว่า "โครงสร้างทุติยภูมิแบบสองชั้น" สำหรับpseudoknot ของ RNA บางชนิด ซึ่งมีรูปแบบเป็นการฝังตัวในหนังสือสองหน้า: ลำดับ RNA ถูกลากไปตามเส้นตรงอีกครั้ง แต่คู่เบสถูกวาดเป็นส่วนโค้งทั้งด้านบนและด้านล่างของเส้นตรงนี้ เพื่อให้เกิดโครงสร้างรองสองระดับ กราฟจะต้องมีดีกรีสูงสุดไม่เกินสาม: แต่ละเบสสามารถมีส่วนร่วมในส่วนโค้งของไดอะแกรมได้เพียงส่วนเดียวเท่านั้น นอกเหนือจากการเชื่อมโยงสองจุดกับเพื่อนบ้านในลำดับเบส ข้อดีของการกำหนดสูตรนี้ได้แก่ ข้อเท็จจริงที่ว่ามันไม่รวมโครงสร้างที่พันกันเป็นปมในอวกาศ และตรงกับปมเทียม RNA ที่รู้จักส่วนใหญ่^{[ 7 ]}

เนื่องจากทราบลำดับของกระดูกสันหลังล่วงหน้าสำหรับการใช้งานนี้ การทดสอบการมีอยู่ของโครงสร้างไบ-เซคันดารีสำหรับการจับคู่เบสที่กำหนดจึงตรงไปตรงมา ปัญหาของการกำหนดขอบให้กับสองหน้าในลักษณะที่เข้ากันได้สามารถกำหนดได้เป็นกรณีของ2-satisfiabilityหรือเป็นปัญหาของการทดสอบความเป็นไบพาร์ไทต์ของกราฟวงกลมที่มีจุดยอดเป็นคู่เบสและขอบอธิบายการตัดกันระหว่างคู่เบส^{[ 7 ]}หรืออีกทางหนึ่งและมีประสิทธิภาพมากกว่า ดังที่ Haslinger & Stadler (1999)แสดง โครงสร้างไบ-เซคันดารีจะมีอยู่ก็ต่อเมื่อกราฟไดอะแกรมของอินพุต (กราฟที่สร้างขึ้นโดยการเชื่อมต่อเบสเข้ากับวงจรตามลำดับและเพิ่มคู่เบสที่กำหนดเป็นขอบ) เป็นกราฟระนาบ [ ^{7 ] ลักษณะ}เฉพาะนี้ทำให้สามารถรับรู้โครงสร้างไบ-เซคันดารีได้ในเวลาเชิงเส้นเป็นกรณีของการทดสอบความเป็นระนาบ

Blin et al. (2007)ใช้การเชื่อมโยงระหว่างโครงสร้างทุติยภูมิและการฝังหนังสือเป็นส่วนหนึ่งของการพิสูจน์ความยากแบบ NPของปัญหาบางอย่างในการเปรียบเทียบโครงสร้างทุติยภูมิของ RNA ^{[ 66 ]}และหากโครงสร้าง RNA เป็นแบบตติยภูมิมากกว่าแบบไบทุติยภูมิ (นั่นคือ หากต้องใช้มากกว่าสองหน้าในแผนภาพ) การกำหนดหมายเลขหน้าก็จะเป็นปัญหา NP-hard อีกครั้ง^{[ 67 ]}

Pavan, Tewari และ Vinodchandran (2012)ใช้การฝังหนังสือเพื่อศึกษาทฤษฎีความซับซ้อนในการคำนวณของ ปัญหา การเข้าถึงในกราฟแบบมีทิศทางดังที่พวกเขาได้สังเกต การเข้าถึงสำหรับกราฟแบบมีทิศทางสองหน้าอาจแก้ไขได้ในพื้นที่ลอการิทึมที่ไม่กำกวม (ซึ่งเป็นอนาล็อกสำหรับความซับซ้อนของพื้นที่ลอการิทึมของคลาสUPของปัญหาเวลาพหุนามที่ไม่กำกวม) อย่างไรก็ตาม การเข้าถึงสำหรับกราฟแบบมีทิศทางสามหน้าต้องใช้พลังทั้งหมดของพื้นที่ลอการิทึมที่ไม่กำหนดดังนั้น การฝังหนังสือจึงดูเหมือนจะเชื่อมโยงอย่างใกล้ชิดกับความแตกต่างระหว่างคลาสความซับซ้อนทั้งสองนี้^{[ 68 ]}

การมีอยู่ของกราฟขยายที่มีหมายเลขหน้าคงที่^{[ 37 ]}เป็นขั้นตอนสำคัญในการพิสูจน์ว่าไม่มีการจำลองเวลาต่ำกว่ากำลังสองของเครื่องทัวริงแบบไม่กำหนด สองเทป โดยเครื่องทัวริงแบบไม่กำหนดหนึ่งเทป^{[ 69 ]}

McKenzie & Overbay (2010)ศึกษาการประยุกต์ใช้ความหนาของหนังสือในพีชคณิตนามธรรมโดยใช้กราฟที่กำหนดจากตัวหารศูนย์ของวงแหวนเฉพาะ ที่จำกัด โดยสร้างจุดยอดสำหรับตัวหารศูนย์แต่ละตัวและขอบสำหรับคู่ค่าแต่ละคู่ที่มีผลคูณเป็นศูนย์^{[ 70 ]}

ในลำดับเอกสารหลายฉบับ Dynnikov ได้ศึกษาการฝังหนังสือเชิงโทโพโลยีของปมและลิงก์โดยแสดงให้เห็นว่าการฝังเหล่านี้สามารถอธิบายได้ด้วยลำดับเชิงคอมบินาทอริกของสัญลักษณ์ และความเท่าเทียมกันเชิงโทโพโลยีของลิงก์สองลิงก์สามารถแสดงได้ด้วยลำดับของการเปลี่ยนแปลงเฉพาะที่ของการฝัง^{[ 71 ] [ 72 ]}