Book embedding
گراف تھیوری میں، بک ایمبیڈنگ ایک کتاب میں سرایت کرنے کے لیے گراف کے پلانر ایمبیڈنگ کی عمومی شکل ہے، آدھے طیاروں کا مجموعہ جس میں ان کی حدود کی طرح ایک ہی لکیر ہوتی ہے۔ عام طور پر، گراف کے عمودی حصوں کو اس باؤنڈری لائن پر ہونا ضروری ہے، جسے ریڑھ کی ہڈی کہا جاتا ہے، اور کناروں کو ایک ہی نصف سطح کے اندر رہنے کی ضرورت ہوتی ہے۔ گراف کی کتاب کی موٹائی گراف کی کسی بھی کتاب کی سرایت کے لیے نصف طیاروں کی سب سے چھوٹی ممکنہ تعداد ہے۔ کتاب کی موٹائی کو پیجن نمبر، اسٹیکن نمبر یا فکسڈ بیرونی موٹائی بھی کہا جاتا ہے۔ بک ایمبیڈنگز کو کئی دیگر گراف غیر متغیرات کی وضاحت کے لیے بھی استعمال کیا گیا ہے جن میں پیج چوڑائی اور بک کراسنگ نمبر شامل ہیں۔ عمودی نقاط والے ہر گراف میں زیادہ سے زیادہ کتاب کی موٹائی ہوتی ہے، اور یہ فارمولا مکمل گراف کے لیے کتاب کی صحیح موٹائی دیتا ہے۔ کتاب کی موٹائی والے گراف بیرونی طیارہ گراف ہیں۔ زیادہ سے زیادہ دو بک موٹائی والے گراف سب ہیملٹنین گراف ہوتے ہیں، جو ہمیشہ پلینر ہوتے ہیں۔ زیادہ عام طور پر، ہر پلینر گراف میں بک موٹائی زیادہ سے زیادہ چار ہوتی ہے۔ تمام معمولی بند گراف خاندانوں، اور خاص طور پر پابند تین چوڑائی یا پابند جینس والے گرافوں میں بھی کتاب کی موٹائی محدود ہوتی ہے۔ کسی دیئے گئے گراف کی صحیح کتاب کی موٹائی کا تعین کرنا NP-مشکل ہے، کتاب کی ریڑھ کی ہڈی کے ساتھ ترتیب دینے والے ایک مقررہ سرے کے ساتھ یا اس کے بغیر۔ گراف کی تین صفحات پر مشتمل کتاب کی سرایت کے وجود کی جانچ، سرایت کی ریڑھ کی ہڈی کے ساتھ عمودی حصوں کی ایک مقررہ ترتیب کو دیکھتے ہوئے، نامعلوم کمپیوٹیشنل پیچیدگی ہے: یہ نہ تو کثیر الجہتی وقت میں حل کرنے کے قابل ہے اور نہ ہی این پی-ہارڈ کے طور پر جانا جاتا ہے۔ کتاب کی سرایت کا مطالعہ کرنے کے اصل محرکات میں سے ایک میں وی ایل ایس آئی ڈیزائن میں ایپلی کیشنز شامل ہیں، جس میں کتاب کی سرایت کے عمودی سرکٹ کے اجزاء کی نمائندگی کرتے ہیں اور تار ان کے درمیان رابطوں کی نمائندگی کرتے ہیں۔ بک ایمبیڈنگ کے گراف ڈرائنگ میں بھی استعمال ہوتے ہیں، جہاں گراف کے لیے دو معیاری بصری انداز، آرک ڈائیگرام اور سرکلر لے آؤٹ، بک ایمبیڈنگ کا استعمال کرتے ہوئے بنائے جا سکتے ہیں۔ نقل و حمل کی منصوبہ بندی میں، پیدل اور گاڑی کی ٹریفک کے مختلف ذرائع اور مقامات جو ٹریفک لائٹ پر ملتے ہیں اور تعامل کرتے ہیں، کو ریاضیاتی طور پر گراف کے عمودی طور پر ماڈل کیا جا سکتا ہے، جس کے کنارے مختلف ماخذ-منزل کے جوڑوں کو جوڑتے ہیں۔ اس گراف کی کتاب کی سرایت کو ایک شیڈول ڈیزائن کرنے کے لیے استعمال کیا جا سکتا ہے جو تمام ٹریفک کو کم سے کم سگنل مراحل کے ساتھ چوراہے کے پار جانے دیتا ہے۔ آر این اے کے فولڈنگ ڈھانچے سے متعلق بائیو انفارمیٹکس کے مسائل میں، ایک صفحے کی کتاب کے سرایت نیوکلک ایسڈ ثانوی ڈھانچے کی کلاسیکی شکلوں کی نمائندگی کرتے ہیں، اور دو صفحات کی کتاب کے سرایت سڈوکنوٹس کی نمائندگی کرتے ہیں۔ کتاب کی سرایت کی دیگر ایپلی کیشنز میں تجریدی الجبرا اور گرہ نظریہ شامل ہیں۔ تاریخ ایک کتاب کے تصور کو، ایک ٹپوولوجیکل اسپیس کے طور پر، 1960 کی دہائی میں سی اے پرسنجر اور گیل ایٹنوسن نے بیان کیا تھا۔ اس کام کے ایک حصے کے طور پر، اٹنیوسن نے پہلے ہی کتابوں میں گراف کو شامل کرنے پر غور کیا۔ انہوں نے جن سرایتوں کا مطالعہ کیا انہوں نے وہی تعریف استعمال کی جو گرافوں کو کسی بھی دوسری ٹپوولوجیکل جگہ میں سرایت کرتی ہے: عمودی مقامات کو الگ الگ نکات سے ظاہر کیا جاتا ہے، کناروں کو منحنی خطوط سے ظاہر کیا جاتا ہے، اور دو کناروں کو ایک دوسرے سے جوڑنے کا واحد طریقہ یہ ہے کہ وہ ایک مشترکہ اختتامی نقطہ پر ملیں۔ 1970 کی دہائی کے اوائل میں، پال سی کینن اور ایل ٹیلر اولمین نے ایک زیادہ محدود قسم کی سرایت تیار کی جو بعد کی زیادہ تر تحقیق میں استعمال ہونے لگی۔ ان کی تشکیل میں، گراف کے عمودی حصوں کو کتاب کی ریڑھ کی ہڈی کے ساتھ رکھا جانا چاہیے، اور ہر کنارے کو ایک صفحے میں ہونا چاہیے۔ کتاب کی سرایت کی بعد کی ترقی میں اہم سنگ میل میں 1980 کی دہائی کے آخر میں میہلس یاناککس کا ثبوت شامل ہے کہ پلانر گراف کی کتاب کی موٹائی زیادہ سے زیادہ چار ہوتی ہے، اور 1990 کی دہائی کے آخر میں کتاب کی سرایت اور بائیو انفارمیٹکس کے درمیان قریبی روابط کی دریافت۔ تعریفیں کتاب ایک خاص قسم کی ٹپوولوجیکل جگہ ہے، جسے نصف طیاروں کا پرستار بھی کہا جاتا ہے۔ یہ ایک واحد لائن پر مشتمل ہوتا ہے، جسے ریڑھ کی ہڈی یا کتاب کا پچھلا حصہ کہا جاتا ہے، اس کے ساتھ ایک یا ایک سے زیادہ آدھے طیاروں کا مجموعہ ہوتا ہے، جسے کتاب کے صفحات یا پتے کہا جاتا ہے، ہر ایک کی ریڑھ کی ہڈی ہوتی ہے۔ صفحات کی ایک محدود تعداد والی کتابوں کو تین جہتی جگہ میں سرایت کیا جا سکتا ہے، مثال کے طور پر کارٹیشین کوآرڈینیٹ سسٹم کا-محور ہونے کا انتخاب کرکے اور صفحات کو نصف طیاروں کے طور پر منتخب کرکے جن کا ڈائیڈرل زاویہ-طیارہ کے حوالے سے ایک عدد ضرب ہے۔ کسی کتاب پر ایک محدود گراف کی کتاب ڈرائنگ اس طرح کی ڈرائنگ ہے کہ اس کے ہر سرے کو ریڑھ کی ہڈی پر ایک نقطہ کے طور پر کھینچا جاتا ہے، اور اس کے ہر کنارے کو ایک منحنی خطوط کے طور پر کھینچا جاتا ہے جو اس کے ایک صفحے کے اندر ہوتا ہے۔ صفحہ بک کراسنگ نمبر صفحہ بک ڈرائنگ میں کراسنگ کی کم از کم تعداد ہے۔ ایک کتاب کی سرایت ایک کتاب ڈرائنگ ہے جو اس میں سرایت کرنے والا گراف بناتی ہے۔ یعنی یہ ایک کتابی ڈرائنگ ہے جس میں کوئی ایج کراسنگ نہیں ہے۔ ہر محدود گراف میں ایک کتاب ہوتی ہے جو کافی تعداد میں صفحات کے ساتھ ایک کتاب پر سرایت کرتی ہے۔ مثال کے طور پر، گراف کے ہر کنارے کو اس کے اپنے الگ صفحے پر سرایت کرنا ہمیشہ ممکن ہے۔ کتاب کی موٹائی، پیجن نمبر، یا اسٹیک نمبر کسی کتاب کو سرایت کرنے کے لیے درکار صفحات کی کم از کم تعداد ہے۔ ایک اور پیمانہ جو سرایت شدہ کتاب کے معیار کی پیمائش کرتا ہے، اس کے صفحات کی تعداد سے آگے، اس کی صفحہ چوڑائی ہے۔ اس کی تعریف کٹ وڈتھ کے مترادف طور پر کناروں کی زیادہ سے زیادہ تعداد کے طور پر کی گئی ہے جسے ایک صفحے کے اندر ریڑھ کی ہڈی پر عمودی کرن کے ذریعے عبور کیا جا سکتا ہے۔ مساوی طور پر (کتاب کے سرایت کے لیے جس میں ہر کنارے کو یک جہتی منحنی خطوط کے طور پر کھینچا جاتا ہے)، یہ ایک ہی صفحے کے اندر کناروں کے ذیلی سیٹ کا زیادہ سے زیادہ سائز ہے کہ کناروں کے اختتامی نکات کے جوڑوں کے ذریعے ریڑھ کی ہڈی پر بیان کردہ وقفے ایک دوسرے کو کاٹتے ہیں۔ ان تعریفوں کے لیے یہ بہت اہم ہے کہ کناروں کو صرف کتاب کے ایک صفحے کے اندر رہنے کی اجازت ہے۔ جیسا کہ اٹنیوسن نے پہلے ہی مشاہدہ کیا ہے، اگر کنارے اس کے بجائے کتاب کی ریڑھ کی ہڈی کے پار ایک صفحے سے دوسرے صفحے پر جا سکتے ہیں، تو ہر گراف کو تین صفحات پر مشتمل کتاب میں سرایت کیا جا سکتا ہے۔ اس طرح کی تین صفحات پر مشتمل ٹپوولوجیکل بک ایمبیڈنگ کے لیے جس میں ریڑھ کی ہڈی کو عبور کرنے کی اجازت ہے، ہر گراف کو زیادہ سے زیادہ ریڑھ کی ہڈی کو عبور کرنے کی لوگرتھمک تعداد کے ساتھ سرایت کیا جا سکتا ہے، اور کچھ گرافوں کو ریڑھ کی ہڈی کو عبور کرنے کی ضرورت ہوتی ہے۔ مخصوص گراف جیسا کہ پہلے اعداد و شمار میں دکھایا گیا ہے، مکمل گراف کی کتاب کی موٹائی تین ہے: غیر پلینر گراف کے طور پر اس کی کتاب کی موٹائی دو سے زیادہ ہے، لیکن تین صفحات پر مشتمل ایک کتاب موجود ہے۔ زیادہ عام طور پر، عمودی کے ساتھ ہر مکمل گراف کی کتاب کی موٹائی بالکل درست ہوتی ہے۔ یہ نتیجہ کسی بھی-ورٹیکس گراف کی زیادہ سے زیادہ ممکنہ کتابی موٹائی پر ایک اوپری حد بھی دیتا ہے۔ مکمل گراف کا دو صفحات پر مشتمل کراسنگ نمبر انتھونی ہل کے ابھی تک غیر مصدقہ قیاس سے میل کھا رہا ہے کہ اس گراف کا غیر محدود کراسنگ نمبر کیا ہونا چاہیے۔ یعنی، اگر ہل کا قیاس درست ہے، تو اس گراف کی ڈرائنگ جو کراسنگ کی تعداد کو کم سے کم کرتی ہے، دو صفحات پر مشتمل ڈرائنگ ہے۔ مکمل دو طرفہ گراف کی کتاب کی موٹائی زیادہ سے زیادہ ہوتی ہے۔ اس کتاب کی موٹائی کے ساتھ ایک ڈرائنگ بنانے کے لیے، دو طرفہ تقسیم کے چھوٹے حصے پر ہر سرے کے لیے، کوئی بھی اس سرے کے ساتھ واقع کناروں کو اپنے صفحے پر رکھ سکتا ہے۔ یہ باؤنڈ ہمیشہ تنگ نہیں ہوتا ؛ مثال کے طور پر، کتاب کی موٹائی تین ہوتی ہے، چار نہیں۔ تاہم، جب گراف کے دونوں اطراف بہت غیر متوازن ہوتے ہیں، اس کے ساتھ، کتاب کی موٹائی بالکل ہوتی ہے۔ ٹورن گراف کے لیے (ایک مکمل ملٹی پارٹیٹ گراف جو ہر آزاد سیٹ کے عمودی حصوں کے آزاد سیٹوں سے بنا ہے، مختلف آزاد سیٹوں کے ہر دو عمودی حصوں کے درمیان ایک کنارے کے ساتھ) کتاب کی موٹائی کو درمیان میں سینڈوچ کیا جاتا ہے اور جب عجیب ہوتا ہے تو اوپری حد کو بہتر بنایا جا سکتا ہے۔ بائنری ڈی بروجن گراف، شفل ایکسچینج گراف، اور مکعب سے منسلک چکروں کی کتاب کی موٹائی (جب یہ گراف غیر طیارہ ہونے کے لیے کافی بڑے ہوتے ہیں) بالکل تین ہوتی ہے۔ خصوصیات منصوبہ بندی اور بیرونی طیارہ کسی دیئے گئے گراف کی کتاب کی موٹائی زیادہ سے زیادہ ایک ہوتی ہے اگر اور صرف اس صورت میں جب وہ بیرونی طیارہ گراف ہو۔ ایک بیرونی طیارہ گراف ایک گراف ہے جس میں ایک طیارہ سرایت ہوتا ہے جس میں تمام عمودی سرایت کے بیرونی چہرے سے تعلق رکھتے ہیں۔ اس طرح کے گراف کے لیے، چوٹیوں کو ریڑھ کی ہڈی کے ساتھ اسی ترتیب میں رکھنا جیسا کہ وہ بیرونی چہرے پر ظاہر ہوتے ہیں، دیئے گئے گراف کی ایک صفحے کی کتاب سرایت فراہم کرتا ہے۔ (گراف کا ایک آرکچولیشن پوائنٹ لازمی طور پر بیرونی چہرے کے ارد گرد عمودی ترتیب میں ایک سے زیادہ بار ظاہر ہوگا، لیکن ان میں سے صرف ایک کاپی کتاب کی سرایت میں شامل کی جانی چاہئے۔) اس کے برعکس، ایک صفحے کی کتاب کی سرایت خود بخود ایک بیرونی سیارہ سرایت ہوتی ہے۔ کیونکہ، اگر ایک گراف ایک ہی صفحے پر سرایت کیا گیا ہے، اور اس کے صفحے کو مکمل سطح تک بڑھانے کے لیے ریڑھ کی ہڈی سے دوسرا نصف سطح منسلک کیا گیا ہے، تو سرایت کے بیرونی چہرے میں پورا اضافی نصف سطح شامل ہوتا ہے، اور تمام عمودی اس بیرونی چہرے پر ہوتے ہیں۔ ہر دو صفحات پر مشتمل کتاب کی سرایت پلانر سرایت کا ایک خاص معاملہ ہے، کیونکہ کسی کتاب کے دو صفحات کا اتحاد ایک جگہ ہے جو ٹپوولوجیکل طور پر پورے سطح کے مساوی ہے۔ لہذا، کتاب کی موٹائی دو والا ہر گراف خود بخود ایک پلانر گراف ہوتا ہے۔ مزید واضح طور پر، گراف کی کتاب کی موٹائی زیادہ سے زیادہ دو ہوتی ہے اگر اور صرف اس صورت میں جب ہیملٹنین سائیکل والے پلانر گراف کا ذیلی گراف ہو۔ اگر کسی گراف کو دو صفحات کا سرایت دیا جاتا ہے، تو اسے ریڑھ کی ہڈی کے ساتھ جو پہلے سے ملحقہ نہیں ہیں، اور ریڑھ کی ہڈی کے پہلے اور آخری عمودی حصوں کے درمیان کسی بھی دو مسلسل عمودی حصوں کے درمیان (کسی بھی صفحہ میں) اضافی کناروں کو شامل کرکے پلانر ہیملٹنین گراف میں بڑھایا جا سکتا ہے۔ گولڈنر-ہیری گراف پلانر گراف کی ایک مثال فراہم کرتا ہے جس میں کتاب کی موٹائی دو نہیں ہوتی ہے: یہ ایک زیادہ سے زیادہ پلانر گراف ہے، لہذا پلانریٹی کو محفوظ رکھتے ہوئے اس میں کوئی کنارے شامل کرنا ممکن نہیں ہے، اور اس میں ہیملٹنین سائیکل نہیں ہے۔ ہیملٹنین چکروں کی طرف سے اس خصوصیت کی وجہ سے، جن گرافوں میں دو صفحات پر مشتمل کتاب کی سرایت ہوتی ہے انہیں سب ہیملٹنین گراف بھی کہا جاتا ہے۔ تمام طیارہ گراف جن کی زیادہ سے زیادہ ڈگری زیادہ سے زیادہ چار ہے ان کی کتاب کی موٹائی زیادہ سے زیادہ دو ہوتی ہے۔ پلانر 3 درختوں کی کتاب کی موٹائی زیادہ سے زیادہ تین ہوتی ہے۔ زیادہ عام طور پر، تمام طیارہ گرافوں میں کتاب کی موٹائی چار ہوتی ہے۔ یہ دعوی میہلس یاناکاکس نے 1986 میں کیا ہے کہ کچھ پلینر گراف موجود ہیں جن کی کتاب کی موٹائی بالکل چار ہے۔ تاہم، اس دعوے کا ایک تفصیلی ثبوت، جس کا اعلان بعد کے جریدے کے مقالے میں کیا گیا تھا، 2020 تک معلوم نہیں تھا، جب بیکوس اور دیگر تھے۔ تین چوڑائی 4 کے ساتھ پلانر گراف پیش کیے گئے جن میں کسی بھی کتاب کی سرایت میں چار صفحات کی ضرورت ہوتی ہے۔ ذیلی تقسیم کے تحت طرز عمل گراف کے ہر کنارے کو دو کنارے والے راستوں میں تقسیم کرنا، ہر کنارے کے اندر نئے عمودی حصے شامل کرنا، بعض اوقات اس کی کتاب کی موٹائی میں اضافہ کر سکتا ہے۔ مثال کے طور پر، ہیرے کے گراف میں کتاب کی موٹائی ایک ہے (یہ بیرونی طیارہ ہے) لیکن اس کی ذیلی تقسیم میں کتاب کی موٹائی دو ہے (یہ طیارہ اور ذیلی ہیملٹنین ہے لیکن بیرونی طیارہ نہیں ہے)۔ تاہم، یہ ذیلی تقسیم کا عمل بعض اوقات ذیلی تقسیم شدہ گراف کی کتاب کی موٹائی کو بھی نمایاں طور پر کم کر سکتا ہے۔ مثال کے طور پر، مکمل گراف کی کتاب کی موٹائی اس کے عمودی حصوں کی تعداد کے متناسب ہوتی ہے، لیکن اس کے ہر کنارے کو دو کنارے والے راستے میں تقسیم کرنے سے ایک ذیلی تقسیم پیدا ہوتا ہے جس کی کتاب کی موٹائی بہت کم ہوتی ہے، صرف۔ اس طرح کی مثالوں کے وجود کے باوجود، یہ قیاس کیا گیا کہ ذیلی تقسیم کی کتاب کی موٹائی اصل گراف سے بہت کم نہیں ہو سکتی۔ خاص طور پر، انہوں نے اندازہ لگایا کہ ایک فنکشن موجود ہے کہ، ہر گراف کے لیے اور ہر کنارے کو دو کنارے والے راستے سے بدل کر بنائے گئے گراف کے لیے، اگر کتاب کی موٹائی ہے تو کتاب کی موٹائی زیادہ سے زیادہ ہے۔ ان کا قیاس غلط ثابت ہوا: ستاروں اور مثلث ٹیلنگ کی کارٹیشین مصنوعات سے بنے گرافوں میں کتاب کی موٹائی بے حد ہوتی ہے، لیکن ان کے کناروں کو چھ کنارے والے راستوں میں تقسیم کرنے سے ان کی کتاب کی موٹائی تین ہو جاتی ہے۔ دیگر گراف غیر متغیرات سے تعلق کتاب کی موٹائی کا تعلق موٹائی سے ہے، جو دیئے گئے گراف کے کناروں کو ڈھانپنے کے لیے درکار پلینر گراف کی تعداد ہے۔ گراف کی موٹائی ہوتی ہے اگر اسے ہوائی جہاز میں کھینچا جا سکے، اور اس کے کناروں کو رنگوں سے رنگا جائے، اس طرح کہ ایک دوسرے کے رنگ کے کناروں کو عبور نہ کریں۔ اسی طرح، گراف میں کتاب کی موٹائی ہوتی ہے اگر اسے نصف سطح میں کھینچا جا سکے، اس کے عمودی حصے نصف سطح کی حد پر ہوتے ہیں، اس کے کناروں کو رنگوں سے رنگا جاتا ہے جس میں ایک ہی رنگ کے دو کناروں کے درمیان کوئی کراسنگ نہیں ہوتی ہے۔ کتاب کی موٹائی کی اس تشکیل میں، کناروں کے رنگ کتاب کے سرایت کے صفحات سے مطابقت رکھتے ہیں۔ تاہم، موٹائی اور کتاب کی موٹائی ایک دوسرے سے بہت مختلف ہو سکتی ہے: ایسے گراف (مکمل گراف کے ذیلی حصے) موجود ہیں جن کی موٹائی دو ہونے کے باوجود کتاب کی موٹائی غیر محدود ہے۔ تین چوڑائی کے گرافوں میں زیادہ سے زیادہ کتاب کی موٹائی ہوتی ہے اور اس کے لیے یہ باؤنڈ تنگ ہوتا ہے۔ کناروں والے گرافوں میں کتاب کی موٹائی ہوتی ہے، اور جینس کے گرافوں میں کتاب کی موٹائی ہوتی ہے۔ زیادہ عام طور پر، ہر معمولی بند گراف خاندان نے کتاب کی موٹائی کو محدود کیا ہے۔ دوسری طرف، 1-پلینر گراف، جو نابالغوں کے نیچے بند نہیں ہوتے ہیں، کتاب کی موٹائی کو بھی محدود کرتے ہیں، لیکن کچھ 1-پلینر گراف بشمول کتاب کی موٹائی کم از کم چار ہوتی ہے۔ باؤنڈ بک موٹائی والے گراف کا ہر اتلی معمولی ایک چھوٹا گراف ہوتا ہے، جس کے کناروں اور عمودی حصوں کا تناسب ایک مستقل سے جڑا ہوتا ہے جو صرف معمولی کی گہرائی اور کتاب کی موٹائی پر منحصر ہوتا ہے۔ یعنی، کی اصطلاحات میں، باؤنڈ بک موٹائی کے گراف نے توسیع کو محدود کیا ہے۔ تاہم، یہاں تک کہ باؤنڈڈ ڈگری کے گراف، جو باؤنڈڈ ایکسٹینشن کے مقابلے میں بہت زیادہ مضبوط ضرورت ہے، میں بھی بک کی بے حد موٹائی ہو سکتی ہے۔ چونکہ کتاب کی موٹائی دو کے گراف پلانر گراف ہوتے ہیں، اس لیے وہ پلانر سیپریٹر تھیوریم کی پابندی کرتے ہیں: ان کے پاس سیپریٹر ہوتے ہیں، عمودی حصوں کے ذیلی سیٹ ہوتے ہیں جن کا ہٹانا گراف کو زیادہ سے زیادہ عمودی حصوں کے ساتھ ٹکڑوں میں تقسیم کرتا ہے، جداکار میں صرف عمودی حصے ہوتے ہیں۔ یہاں، گراف میں عمودی حصوں کی تعداد سے مراد ہے۔ تاہم، کتاب کی موٹائی تین کے گراف موجود ہیں جن میں ذیلی لکیری سائز کے جداکار نہیں ہیں۔ کتاب کی سرایت کے ایک صفحے کے اندر کنارے کچھ طریقوں سے اسٹیک ڈیٹا ڈھانچے کی طرح برتاؤ کرتے ہیں۔ اس کو اسٹیک پر پش اور پاپ آپریشنز کے من مانی ترتیب پر غور کرکے، اور ایک گراف بنا کر باضابطہ بنایا جا سکتا ہے جس میں اسٹیک آپریشنز گراف کے عمودی حصوں سے مطابقت رکھتے ہیں، جو کتاب کی سرایت کی ریڑھ کی ہڈی کے ساتھ ترتیب ترتیب میں رکھے جاتے ہیں۔ پھر، اگر کوئی ہر پاپ آپریشن سے ایک کنارے کو کھینچتا ہے جو اسٹیک سے کسی شے کو پاپ کرتا ہے، پچھلے پش آپریشن کو جو دھکا دیتا ہے، اس کے نتیجے میں گراف میں خود بخود ایک صفحہ کی سرایت ہوگی۔ اس وجہ سے، گراف کے صفحہ نمبر کو اس کا اسٹیک نمبر بھی کہا جاتا ہے۔ اسی طرح، کوئی بھی قطار کے ڈیٹا ڈھانچے کے اینکیو اور ڈیکیو آپریشنز کی صوابدیدی ترتیب پر غور کر سکتا ہے، اور ایک گراف تشکیل دے سکتا ہے جس میں ان کارروائیوں کو اس کے عمودی طور پر رکھا جاتا ہے، جو ایک صفحے کی ریڑھ کی ہڈی پر ترتیب میں رکھا جاتا ہے، جس میں ہر اینکیو آپریشن اور متعلقہ ڈیکیو کے درمیان ایک کنارے ہوتا ہے۔ پھر، اس گراف میں، ہر دو کنارے ریڑھ کی ہڈی پر الگ الگ وقفوں کو عبور کریں گے یا احاطہ کریں گے۔ مشابہت کے لحاظ سے، محققین نے گراف کی قطار کو سرایت کرنے کی تعریف ایک ٹپوولوجیکل کتاب میں اس طرح کی سرایت کے طور پر کی ہے کہ ہر سر ریڑھ کی ہڈی پر واقع ہے، ہر کنارے ایک ہی صفحے پر واقع ہے، اور ایک ہی صفحے کے ہر دو کنارے ریڑھ کی ہڈی پر مختلف وقفوں کو عبور یا احاطہ کرتے ہیں۔ گراف کی قطار کو سرایت کرنے کے لیے درکار صفحات کی کم از کم تعداد کو اس کا قطار نمبر کہا جاتا ہے۔ کمپیوٹیشنل پیچیدگی گراف کی کتاب کی موٹائی تلاش کرنا این پی سخت ہے۔ اس کا نتیجہ اس حقیقت سے نکلتا ہے کہ زیادہ سے زیادہ طیارہ گراف میں ہیملٹنین چکروں کو تلاش کرنا این پی مکمل ہے۔ زیادہ سے زیادہ طیارہ گراف میں، کتاب کی موٹائی دو ہوتی ہے اگر اور صرف اس صورت میں جب ہیملٹنین سائیکل موجود ہو۔ لہذا، یہ جانچنا بھی این پی مکمل ہے کہ آیا دیئے گئے زیادہ سے زیادہ طیارہ گراف کی کتاب کی موٹائی دو ہے۔ اگر کسی سرایت کی ریڑھ کی ہڈی کے ساتھ گراف کے عمودی حصوں کی ترتیب طے کی جاتی ہے، تو دو صفحات پر مشتمل سرایت (اگر یہ موجود ہے) لکیری وقت میں مل سکتی ہے، جو ایک گراف کے لیے پلانریٹی ٹیسٹنگ کی مثال کے طور پر دی گئی گراف کو ان کی ریڑھ کی ترتیب میں عمودی حصوں کو جوڑنے والے سائیکل کے ساتھ بڑھا کر تشکیل دی جاتی ہے۔ دعوی کیا گیا کہ ریڑھ کی فکسڈ آرڈرنگ کے ساتھ تین صفحات کی سرایت تلاش کرنا بھی کثیر الجہتی وقت میں انجام دیا جا سکتا ہے حالانکہ اس کے نتیجے کی تحریر میں بہت سی تفصیلات کو چھوڑ دیا گیا ہے۔ تاہم، ان گرافوں کے لیے جن میں چار یا اس سے زیادہ صفحات کی ضرورت ہوتی ہے، کم سے کم ممکنہ تعداد میں صفحات کے ساتھ سرایت تلاش کرنے کا مسئلہ این پی-سخت رہتا ہے، جو کہ دائرے کے گرافوں کو رنگنے کے این پی-سخت مسئلے کے مساوی ہے، جو ایک دائرے کے کورڈز کے انٹرسیکشن گراف ہیں۔ اس کے عمودی حصوں کے لیے ایک فکسڈ ریڑھ کی ترتیب کے ساتھ ایک گراف کو دیکھتے ہوئے، ان عمودی حصوں کو ایک دائرے کے ارد گرد اسی ترتیب میں کھینچنا اور لائن کے حصوں کے طور پر کناروں کو کھینچنا کورڈز کا مجموعہ تیار کرتا ہے۔ اس کے بعد کوئی بھی ایک دائرہ گراف تشکیل دے سکتا ہے جس میں اس خاکہ کی راگوں کو عمودی طور پر اور راگوں کے جوڑوں کو کناروں کے طور پر عبور کیا جاتا ہے۔ دائرے کے گراف کا رنگ ذیلی سیٹوں میں کناروں کی تقسیم کی نمائندگی کرتا ہے جسے کسی ایک صفحے کو عبور کیے بغیر کھینچا جا سکتا ہے۔ لہذا، ایک بہترین رنگ ایک بہترین کتاب کی سرایت کے برابر ہے۔ چونکہ چار یا اس سے زیادہ رنگوں کے ساتھ سرکل گراف کا رنگ NP-سخت ہوتا ہے، اور چونکہ کسی بھی سرکل گراف کو کسی کتاب کے سرایت کرنے کے مسئلے سے اس طرح بنایا جا سکتا ہے، اس لیے یہ اس بات کی پیروی کرتا ہے کہ بہترین کتاب سرایت بھی NP-سخت ہے۔ دو صفحات پر مشتمل کتابی ڈرائنگ کی ریڑھ کی ہڈی پر فکسڈ ورٹیکس آرڈر کے لیے، جب یہ نمبر غیر صفر ہو تو کراسنگ کی تعداد کو کم کرنا بھی این پی مشکل ہے۔ اگر ریڑھ کی ہڈی کی ترتیب نامعلوم ہے لیکن کناروں کو دو صفحات میں تقسیم کیا گیا ہے، تو ایس پی کیو آر درختوں پر مبنی الگورتھم کے ذریعے لکیری وقت میں 2 صفحات پر مشتمل سرایت (اگر موجود ہے) تلاش کرنا ممکن ہے۔ تاہم، 2 صفحات پر مشتمل سرایت تلاش کرنا این پی مکمل ہے جب نہ تو ریڑھ کی ہڈی کی ترتیب اور نہ ہی کنارے کی تقسیم معلوم ہوتی ہے۔ گراف کے بک کراسنگ نمبر کو تلاش کرنا بھی این پی-مشکل ہے، کیونکہ جانچ کے خصوصی معاملے کی این پی-تکمیل کی وجہ سے کہ آیا 2 صفحات کا کراسنگ نمبر صفر ہے۔ باؤنڈڈ ایکسٹینشن کے نتیجے میں، سب گراف آئسومورفزم کا مسئلہ، یہ معلوم کرنے کا کہ آیا باؤنڈڈ سائز کا پیٹرن گراف کسی بڑے گراف کے سب گراف کے طور پر موجود ہے، لکیری وقت میں حل کیا جا سکتا ہے جب بڑے گراف نے کتاب کی موٹائی کو باؤنڈ کیا ہو۔ یہی بات اس بات کا پتہ لگانے کے لیے بھی درست ہے کہ آیا پیٹرن گراف بڑے گراف کا ایک انڈیوسڈ سب گراف ہے، یا اس میں بڑے گراف کے لیے گراف ہومومورفزم ہے۔ اسی وجہ سے، یہ جانچنے کا مسئلہ کہ آیا باؤنڈ بک موٹائی کا گراف فرسٹ آرڈر منطق کے دیئے گئے فارمولے کی پابندی کرتا ہے، فکسڈ پیرامیٹر ٹریک ایبل ہے۔ مسئلے کو بولین اطمینان بخش مسئلے کی مثال میں تبدیل کرکے اور نتیجے میں آنے والے مسئلے پر ایس اے ٹی حل کنندہ کا اطلاق کرکے بہترین کتاب سرایت تلاش کرنے کے لیے ایک نظام کی وضاحت کریں۔ ان کا کہنا ہے کہ ان کا نظام تقریبا 20 منٹ میں 400-ورٹیکس زیادہ سے زیادہ طیارہ گراف کے لیے ایک بہترین سرایت تلاش کرنے کی صلاحیت رکھتا ہے۔ ایپلی کیشنز غلطی برداشت کرنے والی ملٹی پروسیسنگ کتاب کی سرایت کا مطالعہ کرنے کے اہم محرکات میں سے ایک جس کا حوالہ دیا گیا ہے اس میں غلطی برداشت کرنے والے ملٹی پروسیسرز کی تنظیم کے لیے وی ایل ایس آئی ڈیزائن میں ایک ایپلی کیشن شامل ہے۔ ان مصنفین کے تیار کردہ ڈائیوجینز سسٹم میں، ملٹی پروسیسر سسٹم کے سی پی یوز کو کسی کتاب کی ریڑھ کی ہڈی کے مطابق منطقی ترتیب میں ترتیب دیا جاتا ہے (حالانکہ یہ ترتیب ضروری نہیں کہ اس نظام کی جسمانی ترتیب میں ایک لکیر کے ساتھ رکھی جائے)۔ ان پروسیسرز کو جوڑنے والے مواصلاتی لنکس کو "بنڈلوں" میں گروپ کیا جاتا ہے جو کسی کتاب کے صفحات سے مطابقت رکھتے ہیں اور اسٹیک کی طرح کام کرتے ہیں: ایک پروسیسر کو نئے مواصلاتی لنک کے آغاز سے جوڑنا بنڈل میں پچھلے تمام لنکس کو اوپر کی طرف دھکیل دیتا ہے، اور دوسرے پروسیسر کو مواصلاتی لنک کے آخر تک جوڑنا اسے بنڈل کے نچلے حصے سے جوڑتا ہے اور دوسرے تمام کو نیچے ڈال دیتا ہے۔ اسٹیک کے اس رویے کی وجہ سے، ایک واحد بنڈل مواصلاتی لنکس کے ایک سیٹ کو سنبھال سکتا ہے جو کتاب کی سرایت میں ایک صفحے کے کناروں کو تشکیل دیتا ہے۔ اس طرح سے لنکس کو منظم کرنے سے، مختلف قسم کے نیٹ ورک ٹوپولوجیز کو لاگو کیا جا سکتا ہے، قطع نظر اس کے کہ کون سے پروسیسرز ناقص ہو گئے ہیں، جب تک کہ نیٹ ورک کو لاگو کرنے کے لیے کافی غیر ناقص پروسیسرز باقی رہیں۔ نیٹ ورک ٹوپولوجیز جو اس نظام کے ذریعے نافذ کی جا سکتی ہیں وہ بالکل وہی ہیں جن کی کتاب کی موٹائی زیادہ سے زیادہ دستیاب بنڈلوں کی تعداد کے برابر ہے۔ بک ایمبیڈنگ کا استعمال سرکٹ کی تہوں میں وی ایل ایس آئی اجزاء کو جوڑنے والے تاروں کی جگہ کا نمونہ بنانے کے لیے بھی کیا جا سکتا ہے۔ اسٹیک چھانٹنا ایک اور ایپلی کیشن جس کا حوالہ اسٹیک کا استعمال کرتے ہوئے ترتیبات کو ترتیب دینے کے خدشات سے دیا گیا ہے۔ اس کے ایک بااثر نتیجہ سے پتہ چلتا ہے کہ ایک ایسا نظام جو آنے والے عناصر کو اسٹیک پر دھکیل کر ڈیٹا اسٹریم پر کارروائی کرتا ہے اور پھر، مناسب طریقے سے منتخب کردہ اوقات میں، انہیں اسٹیک سے آؤٹ پٹ اسٹریم پر ڈال کر ڈیٹا کو ترتیب دے سکتا ہے اگر اور صرف اس صورت میں جب اس کی ابتدائی ترتیب کو ایک ترتیب کے ذریعے بیان کیا جائے جو ترتیب کے پیٹرن سے بچتا ہے۔ اس کے بعد سے، اسٹیکس اور قطاروں کے زیادہ عام نظاموں کے ذریعے ڈیٹا اسٹریمز کو ترتیب دینے کے اسی طرح کے مسائل پر بہت کام کیا گیا ہے۔ زیر غور نظام میں، ان پٹ ڈیٹا اسٹریم کے ہر عنصر کو کئی اسٹیکوں میں سے کسی ایک پر دھکیلنا ضروری ہے۔ پھر، ایک بار جب تمام ڈیٹا کو اس طرح دھکیل دیا جاتا ہے، تو آئٹمز کو ان اسٹیکس سے (مناسب ترتیب میں) آؤٹ پٹ اسٹریم پر پاپ کیا جاتا ہے۔ جیسا کہ چنگ اور دیگر۔ مشاہدہ کریں، ایک دی گئی ترتیب کو اس نظام کے ذریعے صرف اس صورت میں ترتیب دیا جا سکتا ہے جب ترتیب سے ماخوذ ایک مخصوص گراف میں ریڑھ کی ہڈی کے ساتھ ایک مخصوص مقررہ ترتیب میں عمودی کے ساتھ ایک کتاب سرایت ہو اور کئی صفحات ہوں جو زیادہ سے زیادہ اسٹیکس کی تعداد کے برابر ہوں۔ ٹریفک کنٹرول جیسا کہ بیان کیا گیا ہے، ایک بک ایمبیڈنگ کو کنٹرولڈ چوراہے پر ٹریفک سگنل کے مراحل کو بیان کرنے کے لیے استعمال کیا جا سکتا ہے۔ ایک چوراہے پر، ٹریفک کی آنے والی اور جانے والی گلیوں (بشمول پیدل چلنے والوں کے کراس واک کے سروں اور سائیکل کی گلیوں کے ساتھ ساتھ موٹر گاڑیوں کے لیے گلیوں) کو گراف کے عمودی حصے کے طور پر پیش کیا جا سکتا ہے، جو جنکشن کے ارد گرد گھڑی کی سمت ترتیب میں سرایت کرنے والی کتاب کی ریڑھ کی ہڈی پر رکھی جاتی ہے۔ آنے والی لین سے باہر جانے والی لین تک پہنچنے کے لیے ٹریفک کے ذریعے لیے گئے چوراہے سے گزرنے والے راستوں کو غیر ہدایت شدہ گراف کے کناروں کے طور پر پیش کیا جا سکتا ہے۔ مثال کے طور پر، اس گراف میں ٹریفک کی آنے والی سے باہر جانے والی لین کا ایک کنارہ ہو سکتا ہے جو دونوں سڑک کے ایک ہی حصے سے تعلق رکھتے ہیں، جو اس حصے سے اس حصے میں واپس یو ٹرن کی نمائندگی کرتا ہے، صرف اس صورت میں جب جنکشن پر یو ٹرن کی اجازت ہو۔ ان کناروں کے دیئے گئے ذیلی سیٹ کے لیے، ذیلی سیٹ راستوں کے ایک مجموعے کی نمائندگی کرتا ہے جو سب ایک دوسرے کی مداخلت کے بغیر عبور کیے جا سکتے ہیں اگر اور صرف اس صورت میں جب ذیلی سیٹ میں کناروں کا کوئی جوڑا شامل نہ ہو جو اس صورت میں عبور کرے گا جب دونوں کناروں کو کسی کتاب کے سرایت کے ایک صفحے میں رکھا گیا ہو۔ اس طرح، اس گراف کی کتاب کی سرایت راستوں کو غیر مداخلت کرنے والے ذیلی سیٹوں میں تقسیم کرنے کی وضاحت کرتی ہے، اور اس گراف کی کتاب کی موٹائی (ریڑھ کی ہڈی پر اس کی مقررہ سرایت کے ساتھ) سگنلنگ شیڈول کے لیے درکار کم از کم مختلف مراحل کی تعداد دیتی ہے جس میں جنکشن کے ذریعے تمام ممکنہ ٹریفک کے راستے شامل ہیں۔ گراف ڈرائنگ بک ایمبیڈنگ کو اکثر نیٹ ورک ڈیٹا کے تصور میں بھی لاگو کیا گیا ہے۔ گراف ڈرائنگ میں دو معیاری لے آؤٹ، آرک ڈائیگرام اور سرکلر لے آؤٹ، کو بک ایمبیڈنگ کے طور پر دیکھا جا سکتا ہے، اور بک ایمبیڈنگ کو کلسٹرڈ لے آؤٹ، بیک وقت ایمبیڈنگ، اور تین جہتی گراف ڈرائنگ کی تعمیر میں بھی لاگو کیا گیا ہے۔ ایک آرک ڈائیگرام یا لکیری ایمبیڈنگ گراف کے عمودی حصوں کو ایک لکیر کے ساتھ رکھتا ہے، اور گراف کے کناروں کو اس لکیر کے اوپر یا نیچے سیمی سرکلز کے طور پر کھینچتا ہے، بعض اوقات لائن کے حصوں پر کناروں کو کھینچنے کی بھی اجازت دیتا ہے۔ یہ ڈرائنگ سٹائل ایک صفحہ (اگر تمام سیمی سرکلز لائن کے اوپر ہیں) یا دو صفحات (اگر لائن کے دونوں اطراف استعمال کیے جاتے ہیں) کے ساتھ سرایت کرنے والی کتاب سے مطابقت رکھتا ہے، اور اسے اصل میں گراف کے کراسنگ نمبروں کا مطالعہ کرنے کے طریقے کے طور پر متعارف کرایا گیا تھا۔ پلانر گراف جن میں دو صفحات پر مشتمل کتاب کی سرایت نہیں ہوتی ہے، ان کے کناروں کو لائن کے اوپر اور نیچے متعدد سیمی سرکلز کے ذریعے ظاہر کرنے کی اجازت دے کر بھی اسی طرح سے تیار کیا جا سکتا ہے۔ اس طرح کی ڈرائنگ معمول کی تعریف کے مطابق سرایت شدہ کتاب نہیں ہے، بلکہ اسے ٹپوولوجیکل بک سرایت کہا جاتا ہے۔ ہر پلانر گراف کے لیے، ایسی سرایت تلاش کرنا ہمیشہ ممکن ہے جس میں ہر کنارہ زیادہ سے زیادہ ایک بار ریڑھ کی ہڈی کو عبور کرے۔ ایک اور ڈرائنگ سٹائل میں، سرکلر لے آؤٹ، گراف کے عمودی حصوں کو ایک دائرے پر رکھا جاتا ہے اور کناروں کو دائرے کے اندر یا باہر کھینچا جاتا ہے۔ پھر، دائرے کے اندر کناروں کی جگہ کا تعین (مثال کے طور پر سیدھی لکیر کے حصوں کے طور پر) ایک صفحے کی کتاب کے ڈرائنگ سے مطابقت رکھتا ہے، جبکہ دائرے کے اندر اور باہر دونوں جگہ کا تعین دو صفحات کی کتاب کے ڈرائنگ سے مطابقت رکھتا ہے۔ کسی بھی انداز کے ایک صفحے کے ڈرائنگ کے لیے، ڈرائنگ کی بصری بے ترتیبی کو کم کرنے کے لیے کراسنگ کی تعداد کو چھوٹا رکھنا ضروری ہے۔ کراسنگ کی تعداد کو کم کرنا این پی مکمل ہے، لیکن عمودی کی تعداد کہاں ہے اس کے تخمینہ تناسب کے ساتھ اس کا تخمینہ لگایا جا سکتا ہے۔ ایک صفحے یا دو صفحات کے کراسنگ نمبر کو کم سے کم کرنا فکسڈ پیرامیٹر ٹریکٹ ایبل ہوتا ہے جب دیئے گئے گراف کے سائکلومیٹک نمبر، یا کراسنگ نمبر اور گراف کی تین چوڑائی کے امتزاج سے پیرامیٹرائز کیا جاتا ہے۔ کراسنگ کی پیچیدگی کو کم کرنے کے لیے تحقیقی طریقے بھی وضع کیے گئے ہیں، مثال کے طور پر۔ محتاط ورٹیکس اندراج کے ترتیب پر اور مقامی اصلاح پر۔ صفحات میں کناروں کی ایک مقررہ تقسیم کے ساتھ دو صفحات پر مشتمل کتاب کی سرایت کو کلسٹرڈ پلانریٹی کی ایک شکل کے طور پر سمجھا جا سکتا ہے، جس میں دیئے گئے گراف کو اس طرح سے کھینچا جانا چاہیے کہ گراف کے کچھ حصے (کناروں کے دو ذیلی سیٹ) ڈرائنگ میں اس طرح رکھے جائیں جو ان کے کلسٹرنگ کی عکاسی کرتے ہیں۔ گراف کی بیک وقت سرایت تلاش کرنے کے لیے دو صفحات پر مشتمل کتاب سرایت کا بھی استعمال کیا گیا ہے، جس میں ایک ہی ورٹیکس سیٹ پر دو گراف دیے گئے ہیں اور کسی کو ان عمودی حصوں کے لیے ایک جگہ تلاش کرنی چاہیے جس میں دونوں گراف سیدھے کناروں کے ساتھ ہموار طریقے سے تیار کیے گئے ہیں۔ گراف کی سہ جہتی ڈرائنگ بنانے کے لیے دو سے زیادہ صفحات والی کتاب کے سرایت کا بھی استعمال کیا گیا ہے۔ خاص طور پر، کم حجم کے تین جہتی گرڈ میں گراف کو سرایت کرنے کے طریقہ کار کے حصے کے طور پر، کتاب کے سرایت کے لیے ایک تعمیر کا استعمال کیا گیا جو ہر صفحے کے اندر ہر سرے کی ڈگری کو کم رکھتا ہے۔ آر این اے فولڈنگ اس مطالعے میں کہ آر این اے مالیکیولز کس طرح اپنی ساخت بنانے کے لیے فولڈ ہوتے ہیں، نیوکلک ایسڈ ثانوی ڈھانچے کی معیاری شکل کو خاکہ کے طور پر اڈوں کی ایک زنجیر (خود آر این اے ترتیب) کے طور پر بیان کیا جا سکتا ہے، جو ایک لکیر کے ساتھ کھینچا جاتا ہے، جس میں ڈھانچے کے بیس پیئرز کو بیان کرنے والی لکیر کے اوپر آرکس کا مجموعہ ہوتا ہے۔ یعنی، اگرچہ ان ڈھانچوں کی دراصل ایک پیچیدہ تین جہتی شکل ہوتی ہے، لیکن ان کے رابطے (جب ایک ثانوی ڈھانچہ موجود ہوتا ہے) کو زیادہ تجریدی ڈھانچے، ایک صفحے کی کتاب کے سرایت کے ذریعے بیان کیا جا سکتا ہے۔ تاہم، تمام آر این اے فولڈز اس آسان طریقے سے برتاؤ نہیں کرتے ہیں۔ کچھ آر این اے سیڈوکنوٹس کے لیے ایک نام نہاد "بائی سیکنڈری ڈھانچہ" تجویز کیا ہے جو دو صفحات پر مشتمل کتاب کی سرایت کی شکل اختیار کرتا ہے: آر این اے کی ترتیب کو دوبارہ ایک لکیر کے ساتھ کھینچا جاتا ہے، لیکن بیس پیئرز کو اس لکیر کے اوپر اور نیچے دونوں طرف آرکس کے طور پر کھینچا جاتا ہے۔ دو ثانوی ڈھانچہ بنانے کے لیے، گراف میں زیادہ سے زیادہ تین ڈگری ہونی چاہیے: ہر بیس بنیادی ترتیب میں اپنے پڑوسیوں کے دو لنکس کے علاوہ، خاکہ کے صرف ایک آرک میں حصہ لے سکتا ہے۔ اس تشکیل کے فوائد میں یہ حقائق شامل ہیں کہ اس میں وہ ڈھانچے شامل نہیں ہیں جو دراصل خلا میں بندھے ہوئے ہیں، اور یہ کہ یہ سب سے زیادہ معروف آر این اے سڈوکنوٹس سے میل کھاتا ہے۔ چونکہ اس ایپلی کیشن کے لیے ریڑھ کی ہڈی کی ترتیب پہلے سے معلوم ہے، اس لیے دی گئی بیس پیئرنگ کے لیے دو ثانوی ڈھانچے کے وجود کی جانچ کرنا سیدھا ہے۔ دو صفحات کو ہم آہنگ طریقے سے کناروں کو تفویض کرنے کے مسئلے کو یا تو 2-اطمینان کی مثال کے طور پر، یا دائرے کے گراف کی دو طرفہ جانچ کے مسئلے کے طور پر وضع کیا جا سکتا ہے جس کے عمودی حصے بیس پیئر ہیں اور جن کے کنارے بیس پیئر کے درمیان کراسنگ کو بیان کرتے ہیں۔ متبادل طور پر اور زیادہ مؤثر طریقے سے، جیسا کہ ظاہر ہوتا ہے، ایک دو ثانوی ڈھانچہ اس صورت میں موجود ہوتا ہے جب ان پٹ کا خاکہ گراف (ایک گراف جو اڈوں کو ان کی ترتیب کی ترتیب میں ایک سائیکل میں جوڑ کر اور دیئے گئے بیس پیئرز کو کناروں کے طور پر شامل کرکے بنایا گیا ہو) ایک پلانر گراف ہو۔ یہ خصوصیت دو ثانوی ڈھانچوں کو لکیری وقت میں طیاروں کی جانچ کی مثال کے طور پر تسلیم کرنے کی اجازت دیتی ہے۔ ثانوی ڈھانچے اور بک ایمبیڈنگ کے درمیان تعلق کو آر این اے ثانوی ڈھانچے کے موازنہ میں کچھ مسائل کی این پی سختی کے ثبوت کے حصے کے طور پر استعمال کیا۔ اور اگر کوئی آر این اے ڈھانچہ دو ثانوی کے بجائے ترتیری ہے (یعنی، اگر اسے اپنے خاکہ میں دو سے زیادہ صفحات کی ضرورت ہو)، تو صفحہ نمبر کا تعین کرنا دوبارہ این پی ہارڈ ہے۔ کمپیوٹیشنل پیچیدگی کے نظریہ نے ہدایت شدہ گرافوں میں رسائی کے مسئلے کے کمپیوٹیشنل پیچیدگی کے نظریہ کا مطالعہ کرنے کے لیے کتابی سرایت کا استعمال کیا۔ جیسا کہ انہوں نے مشاہدہ کیا ہے، دو صفحات کے ڈائریکٹڈ گراف کی رسائی کو غیر واضح لوگرتھمک اسپیس (اینالاگ، لوگرتھمک اسپیس پیچیدگی کے لیے، غیر واضح کثیر الجہتی وقت کے مسائل کی کلاس یو پی کا) میں حل کیا جا سکتا ہے۔ تاہم، تین صفحات کے ڈائریکٹڈ گراف کے لیے رسائی کے لیے غیر متعین لوگرتھمک اسپیس کی مکمل طاقت کی ضرورت ہوتی ہے۔ اس طرح، کتاب کی سرایت ان دو پیچیدگی کلاسوں کے درمیان فرق کے ساتھ گہرا جڑا ہوا معلوم ہوتا ہے۔ مستقل پیج نمبر کے ساتھ ایکسپینڈر گراف کا وجود یہ ثابت کرنے کے لیے کلیدی قدم ہے کہ ایک ٹیپ غیر تعیناتی ٹورنگ مشینوں کے ذریعے دو ٹیپ غیر تعیناتی ٹورنگ مشینوں کا کوئی ذیلی کواڈریٹک ٹائم تخروپن نہیں ہے۔ ریاضی کے دیگر شعبے تجریدی الجبرا میں کتاب کی موٹائی کی ایپلی کیشنز کا مطالعہ کرتے ہیں، ہر صفر تقسیم کار کے لیے ایک ورٹیکس اور اقدار کے ہر جوڑے کے لیے ایک کنارہ بنا کر ایک محدود مقامی رنگ کے صفر تقسیم کاروں سے بیان کردہ گراف کا استعمال کرتے ہوئے جس کا پروڈکٹ صفر ہے۔ ایک کثیر کاغذ کے سلسلے میں، ڈینیکوف نے گانٹھوں اور لنکس کی ٹپوولوجیکل کتاب کی سرایت کا مطالعہ کیا ہے، جس سے یہ ظاہر ہوتا ہے کہ ان سرایتوں کو علامتوں کی مشترکہ ترتیب سے بیان کیا جا سکتا ہے اور یہ کہ دو لنکس کی ٹپوولوجیکل مساوات کو مقامی تبدیلیوں کے سلسلے سے ظاہر کیا جا سکتا ہے۔ سرایت میں۔ حوالہ جات ٹوپوولوجیکل گراف تھیوری