Book embedding
গ্রাফ তত্ত্বে, একটি বই এম্বেডিং হল একটি বইতে এম্বেডিং করার জন্য একটি গ্রাফের প্ল্যানার এম্বেডিংয়ের একটি সাধারণীকরণ, অর্ধ-সমতলের একটি সংগ্রহ যার সবগুলিরই সীমানার মতো একই রেখা রয়েছে। সাধারণত, গ্রাফের শীর্ষগুলি এই সীমানা রেখায় থাকা প্রয়োজন, যাকে মেরুদণ্ড বলা হয় এবং প্রান্তগুলি একটি একক অর্ধ-সমতলের মধ্যে থাকা প্রয়োজন। একটি গ্রাফের বইয়ের পুরুত্ব হল গ্রাফের যে কোনও বই এম্বেডিংয়ের জন্য অর্ধ-সমতলের সম্ভাব্য ক্ষুদ্রতম সংখ্যা। বইয়ের পুরুত্বকে প্যাজেনম্বার, স্ট্যাকনাম্বার বা স্থির বাইরের পুরুত্বও বলা হয়। পেজউইথ এবং বুক ক্রসিং নম্বর সহ আরও বেশ কয়েকটি গ্রাফ অপরিবর্তনীয় সংজ্ঞায়িত করতে বই এম্বেডিং ব্যবহার করা হয়েছে। শীর্ষযুক্ত প্রতিটি গ্রাফের সর্বাধিক বইয়ের পুরুত্ব থাকে এবং এই সূত্রটি সম্পূর্ণ গ্রাফের জন্য সঠিক বইয়ের পুরুত্ব দেয়। বইয়ের পুরুত্বের গ্রাফগুলি হল বাইরের সমতলীয় গ্রাফ। সর্বাধিক দুটি বইয়ের পুরুত্ব সহ গ্রাফগুলি হল সাবহ্যামিলটোনিয়ান গ্রাফ, যা সর্বদা সমতলীয় হয়; আরও সাধারণভাবে, প্রতিটি সমতলীয় গ্রাফের বইয়ের পুরুত্ব সর্বাধিক চারটি থাকে। সমস্ত ক্ষুদ্র-বদ্ধ গ্রাফ পরিবার এবং বিশেষত আবদ্ধ ত্রি-প্রস্থ বা আবদ্ধ গণের গ্রাফগুলিরও আবদ্ধ বইয়ের পুরুত্ব রয়েছে। একটি প্রদত্ত গ্রাফের সঠিক বইয়ের পুরুত্ব নির্ধারণ করা এনপি-কঠিন, বইয়ের মেরুদণ্ড বরাবর একটি নির্দিষ্ট শীর্ষক্রম সহ বা না জেনে। একটি গ্রাফের তিন পৃষ্ঠার বই এম্বেডিংয়ের অস্তিত্ব পরীক্ষা করা, এম্বেডিংয়ের মেরুদণ্ড বরাবর শীর্ষগুলির একটি নির্দিষ্ট ক্রম দেওয়া, অজানা গণনামূলক জটিলতা রয়েছেঃ এটি বহুপদী সময়ে সমাধানযোগ্য বা এনপি-হার্ড হিসাবে পরিচিত নয়। বই এম্বেডিং অধ্যয়নের মূল অনুপ্রেরণাগুলির মধ্যে একটি হল ভি. এল. এস. আই নকশার প্রয়োগ, যেখানে একটি বই এম্বেডিংয়ের শীর্ষগুলি একটি সার্কিটের উপাদানগুলির প্রতিনিধিত্ব করে এবং তারগুলি তাদের মধ্যে সংযোগের প্রতিনিধিত্ব করে। বই এম্বেডিংয়ের গ্রাফ অঙ্কনেও প্রয়োগ রয়েছে, যেখানে গ্রাফের জন্য দুটি স্ট্যান্ডার্ড ভিজ্যুয়ালাইজেশন শৈলী, আর্ক ডায়াগ্রাম এবং বৃত্তাকার বিন্যাস, বই এম্বেডিং ব্যবহার করে তৈরি করা যেতে পারে। পরিবহন পরিকল্পনায়, ট্র্যাফিক লাইটে মিলিত হওয়া এবং মিথস্ক্রিয়া করা পদচারণা এবং যানবাহন ট্র্যাফিকের বিভিন্ন উৎস এবং গন্তব্যগুলিকে গাণিতিকভাবে একটি গ্রাফের শীর্ষ হিসাবে মডেল করা যেতে পারে, যার প্রান্তগুলি বিভিন্ন উৎস-গন্তব্য জোড়াকে সংযুক্ত করে। এই গ্রাফের একটি বই এম্বেডিং একটি সময়সূচী তৈরি করতে ব্যবহার করা যেতে পারে যা সমস্ত ট্র্যাফিককে যতটা সম্ভব কম সংকেত পর্যায় সহ ছেদ জুড়ে যেতে দেয়। আর. এন. এ-র ভাঁজ কাঠামোর সাথে জড়িত বায়োইনফরমেটিক্স সমস্যাগুলিতে, একক-পৃষ্ঠার বইয়ের এম্বেডিংগুলি নিউক্লিক অ্যাসিড গৌণ কাঠামোর শাস্ত্রীয় রূপগুলির প্রতিনিধিত্ব করে এবং দুই-পৃষ্ঠার বইয়ের এম্বেডিংগুলি সিউডোকনটসের প্রতিনিধিত্ব করে। বই এম্বেডিংয়ের অন্যান্য প্রয়োগের মধ্যে রয়েছে বিমূর্ত বীজগণিত এবং গিঁট তত্ত্ব। 1960-এর দশকে সি. এ. পার্সিঙ্গার এবং গেইল অ্যাটনিওসেন একটি বইয়ের ধারণাকে একটি ভূতাত্ত্বিক স্থান হিসাবে সংজ্ঞায়িত করেছিলেন। এই কাজের অংশ হিসাবে, অ্যাটনিওসেন ইতিমধ্যে বইগুলিতে গ্রাফ এম্বেড করার কথা বিবেচনা করেছেন। তিনি যে এম্বেডিংগুলি অধ্যয়ন করেছিলেন সেগুলি অন্য যে কোনও টপোলজিকাল স্পেসে গ্রাফের এম্বেডিংয়ের মতো একই সংজ্ঞা ব্যবহার করেঃ শীর্ষগুলি স্বতন্ত্র বিন্দু দ্বারা প্রতিনিধিত্ব করা হয়, প্রান্তগুলি বক্ররেখা দ্বারা প্রতিনিধিত্ব করা হয় এবং দুটি প্রান্ত ছেদ করার একমাত্র উপায় হল তাদের জন্য একটি সাধারণ শেষ বিন্দুতে মিলিত হওয়া। 1970-এর দশকের গোড়ার দিকে, পল সি কাইনেন এবং এল টেলর ওলম্যান আরও সীমাবদ্ধ ধরনের এম্বেডিং তৈরি করেছিলেন যা পরবর্তী বেশিরভাগ গবেষণায় ব্যবহৃত হয়েছিল। তাদের গঠনে, গ্রাফের শীর্ষগুলি অবশ্যই বইয়ের মেরুদণ্ড বরাবর স্থাপন করতে হবে এবং প্রতিটি প্রান্ত অবশ্যই একটি পৃষ্ঠায় থাকতে হবে। বইয়ের এম্বেডিংয়ের পরবর্তী বিকাশের গুরুত্বপূর্ণ মাইলফলকগুলির মধ্যে রয়েছে 1980-এর দশকের শেষের দিকে মিহালিস ইয়ানাকাকিসের প্রমাণ যে প্ল্যানার গ্রাফের বইয়ের পুরুত্ব সর্বাধিক চারটি এবং 1990-এর দশকের শেষের দিকে বইয়ের এম্বেডিং এবং বায়োইনফরম্যাটিক্সের মধ্যে ঘনিষ্ঠ সংযোগের আবিষ্কার। সংজ্ঞা একটি বই হল একটি নির্দিষ্ট ধরনের টপোলজিকাল স্থান, যাকে অর্ধ-সমতলের ফ্যানও বলা হয়। এটি একটি একক রেখা নিয়ে গঠিত, যাকে বইয়ের মেরুদণ্ড বা পিছন বলা হয়, এক বা একাধিক অর্ধ-সমতলের সংগ্রহ সহ, যাকে বইয়ের পৃষ্ঠা বা পাতা বলা হয়, যার প্রত্যেকটির সীমানা মেরুদণ্ড। সীমিত সংখ্যক পৃষ্ঠা সহ বইগুলি ত্রিমাত্রিক স্থানে এম্বেড করা যেতে পারে, উদাহরণস্বরূপ একটি কার্টেসিয়ান স্থানাঙ্ক ব্যবস্থার-অক্ষ হিসাবে বেছে নিয়ে এবং পৃষ্ঠাগুলি অর্ধ-সমতল হিসাবে বেছে নিয়ে যার ডাইহেড্রাল কোণটি-সমতলের সাপেক্ষে একটি পূর্ণসংখ্যা গুণিতক। একটি বইয়ের উপর একটি সীমাবদ্ধ গ্রাফের একটি বই অঙ্কন এমন একটি অঙ্কন যা এর প্রতিটি শীর্ষকে মেরুদণ্ডের উপর একটি বিন্দু হিসাবে আঁকা হয় এবং এর প্রতিটি প্রান্ত একটি বক্ররেখা হিসাবে আঁকা হয় যা একটি বইয়ের একক পৃষ্ঠার মধ্যে থাকে। - পৃষ্ঠা বই ক্রসিং নম্বর হল একটি-পৃষ্ঠা বইয়ের অঙ্কনে ক্রসিংয়ের সর্বনিম্ন সংখ্যা। একটি বই এম্বেডিং হল একটি বইয়ের অঙ্কন যা একটি গ্রাফ এম্বেডিং গঠন করে। অর্থাৎ, এটি একটি বইয়ের অঙ্কন যার কোনও প্রান্ত ক্রসিং নেই। প্রতিটি সীমাবদ্ধ গ্রাফের একটি বই থাকে যা একটি বইয়ের উপর যথেষ্ট সংখ্যক পৃষ্ঠা সহ এম্বেড করা থাকে। উদাহরণস্বরূপ, গ্রাফের প্রতিটি প্রান্তকে তার নিজস্ব পৃথক পৃষ্ঠায় এম্বেড করা সর্বদা সম্ভব। বইয়ের পুরুত্ব, প্যাজেন নম্বর বা স্ট্যাক নম্বর হল একটি বই এম্বেড করার জন্য প্রয়োজনীয় সর্বনিম্ন সংখ্যক পৃষ্ঠা। আরেকটি মাপকাঠি যা একটি বইয়ের এম্বেডিংয়ের গুণমান পরিমাপ করে, তার পৃষ্ঠার সংখ্যার বাইরে, তার পৃষ্ঠা প্রস্থ। এটি কাটউইথের অনুরূপভাবে সংজ্ঞায়িত করা হয় একটি একক পৃষ্ঠার মধ্যে মেরুদণ্ডের লম্বভাবে একটি রশ্মি দ্বারা অতিক্রম করা যেতে পারে এমন প্রান্তের সর্বাধিক সংখ্যা হিসাবে। সমতুল্যভাবে (বই এম্বেডিংয়ের জন্য যেখানে প্রতিটি প্রান্ত একঘেয়ে বক্ররেখা হিসাবে আঁকা হয়), এটি একটি একক পৃষ্ঠার মধ্যে প্রান্তের একটি উপসেটের সর্বোচ্চ আকার যাতে প্রান্তের প্রান্তবিন্দুগুলির জোড়া দ্বারা মেরুদণ্ডের উপর সংজ্ঞায়িত ব্যবধানগুলি একে অপরকে ছেদ করে। এই সংজ্ঞাগুলির জন্য এটি অত্যন্ত গুরুত্বপূর্ণ যে প্রান্তগুলি কেবল বইয়ের একটি পৃষ্ঠার মধ্যে থাকার অনুমতি দেওয়া হয়। অ্যাটনিওসেন ইতিমধ্যে পর্যবেক্ষণ করেছেন, যদি প্রান্তগুলি বইয়ের মেরুদণ্ড জুড়ে এক পৃষ্ঠা থেকে অন্য পৃষ্ঠায় যেতে পারে, তবে প্রতিটি গ্রাফ তিন পৃষ্ঠার বইতে এম্বেড করা যেতে পারে। এই ধরনের তিন পৃষ্ঠার টপোলজিক্যাল বইয়ের জন্য যেখানে মেরুদণ্ডের ক্রসিং অনুমোদিত, প্রতিটি গ্রাফকে প্রতি প্রান্তে সর্বাধিক সংখ্যক মেরুদণ্ডের ক্রসিং দিয়ে এম্বেড করা যেতে পারে এবং কিছু গ্রাফের জন্য এই অনেক মেরুদণ্ডের ক্রসিংয়ের প্রয়োজন হয়। নির্দিষ্ট গ্রাফ প্রথম চিত্রে যেমন দেখানো হয়েছে, সম্পূর্ণ গ্রাফের বইয়ের পুরুত্ব তিনটিঃ একটি নন-প্ল্যানার গ্রাফ হিসাবে এর বইয়ের পুরুত্ব দুটির চেয়ে বেশি, তবে তিনটি পৃষ্ঠা সহ একটি বই রয়েছে। আরও সাধারণভাবে, শীর্ষ সহ প্রতিটি সম্পূর্ণ গ্রাফের বইয়ের পুরুত্ব ঠিক। এই ফলাফলটি যে কোনও-ভার্টেক্স গ্রাফের সর্বাধিক সম্ভাব্য বইয়ের পুরুত্বের উপর একটি ঊর্ধ্বসীমাও দেয়। সম্পূর্ণ গ্রাফের দুই পৃষ্ঠার ক্রসিং নম্বরটি অ্যান্টনি হিলের এখনও অপ্রমাণিত অনুমানের সাথে মিলে যাচ্ছে যে এই গ্রাফের অবাধ ক্রসিং নম্বরটি কী হওয়া উচিত। অর্থাৎ, যদি হিলের অনুমান সঠিক হয়, তবে এই গ্রাফের অঙ্কন যা ক্রসিংয়ের সংখ্যাকে ন্যূনতম করে তা হল দুই পৃষ্ঠার অঙ্কন। সম্পূর্ণ দ্বিদলীয় গ্রাফের বইয়ের পুরুত্ব সর্বাধিক। এই বইয়ের পুরুত্ব দিয়ে একটি অঙ্কন তৈরি করতে, দ্বিদলীয় বিভাজনের ছোট দিকের প্রতিটি শীর্ষের জন্য, কেউ তাদের নিজস্ব পৃষ্ঠায় সেই শীর্ষের সাথে সংযুক্ত প্রান্তগুলি স্থাপন করতে পারে। এই বন্ধন সবসময় আঁটসাঁট হয় না; উদাহরণস্বরূপ, বইয়ের পুরুত্ব চার নয়, তিন। যাইহোক, যখন গ্রাফের দুটি দিক খুব ভারসাম্যহীন হয়, তখন এর বইয়ের পুরুত্ব ঠিক হয়। তুরান গ্রাফের জন্য (একটি সম্পূর্ণ মাল্টিপার্টাইট গ্রাফ যা প্রতি স্বাধীন সেটের শীর্ষগুলির স্বাধীন সেট থেকে গঠিত, বিভিন্ন স্বাধীন সেটের প্রতিটি দুটি শীর্ষের মধ্যে একটি প্রান্ত সহ) বইয়ের পুরুত্বের মধ্যে স্যান্ডউইচ করা হয় এবং যখন বিজোড় হয় তখন উপরের সীমাটি উন্নত করা যেতে পারে বাইনারি ডি ব্রুইন গ্রাফ, শাফল-এক্সচেঞ্জ গ্রাফ এবং কিউব-সংযুক্ত চক্রের বইয়ের পুরুত্ব (যখন এই গ্রাফগুলি ননপ্ল্যানার হওয়ার জন্য যথেষ্ট বড় হয়) ঠিক তিনটি। বৈশিষ্ট্য প্ল্যানারিটি এবং আউটারপ্ল্যানারিটি একটি প্রদত্ত গ্রাফের বইয়ের পুরুত্ব সর্বাধিক এক হয় যদি এবং শুধুমাত্র একটি বাইরের প্ল্যানার গ্রাফ হয়। একটি আউটারপ্ল্যানার গ্রাফ হল এমন একটি গ্রাফ যার একটি প্ল্যানার এম্বেডিং রয়েছে যেখানে সমস্ত শীর্ষগুলি এম্বেডিংয়ের বাইরের মুখের অন্তর্গত। এই ধরনের গ্রাফের জন্য, মেরুদণ্ড বরাবর শীর্ষগুলি বাইরের মুখের মতো একই ক্রমে স্থাপন করা প্রদত্ত গ্রাফের এক পৃষ্ঠার বই এম্বেডিং প্রদান করে। (গ্রাফের একটি উচ্চারণ বিন্দু অবশ্যই বাইরের মুখের চারপাশে শীর্ষগুলির চক্রাকার ক্রমে একাধিকবার উপস্থিত হবে, তবে সেই অনুলিপিগুলির মধ্যে কেবল একটি বই এম্বেডিংয়ে অন্তর্ভুক্ত করা উচিত।) অন্যদিকে, এক পৃষ্ঠার বই এম্বেডিং স্বয়ংক্রিয়ভাবে একটি বাইরের প্ল্যানার এম্বেডিং। কারণ, যদি একটি গ্রাফ একটি একক পৃষ্ঠায় এম্বেড করা থাকে এবং একটি সম্পূর্ণ সমতলে প্রসারিত করার জন্য মেরুদণ্ডের সাথে আরেকটি অর্ধ-তল সংযুক্ত করা হয়, তবে এম্বেডিংয়ের বাইরের মুখটি পুরো যোগ করা অর্ধ-তলকে অন্তর্ভুক্ত করে এবং সমস্ত শীর্ষগুলি এই বাইরের মুখের উপর অবস্থিত। প্রতিটি দুই পৃষ্ঠার বই এম্বেডিং একটি প্ল্যানার এম্বেডিংয়ের একটি বিশেষ কেস, কারণ একটি বইয়ের দুটি পৃষ্ঠার মিলন পুরো সমতলের সমতুল্য একটি স্থান। অতএব, বইয়ের পুরুত্ব দুই সহ প্রতিটি গ্রাফ স্বয়ংক্রিয়ভাবে একটি সমতলীয় গ্রাফ। আরও সুনির্দিষ্টভাবে বলতে গেলে, একটি গ্রাফের বইয়ের পুরুত্ব সর্বাধিক দুই হয় যদি এবং শুধুমাত্র হ্যামিল্টনিয়ান চক্রযুক্ত একটি সমতলীয় গ্রাফের একটি উপগ্রাফ হয়। যদি একটি গ্রাফকে দুই পৃষ্ঠার এম্বেডিং দেওয়া হয়, তবে এটি মেরুদণ্ড বরাবর যে কোনও পরপর দুটি শীর্ষের মধ্যে (যে কোনও পৃষ্ঠায়) অতিরিক্ত প্রান্ত যোগ করে একটি প্ল্যানার হ্যামিল্টনিয়ান গ্রাফে বর্ধিত করা যেতে পারে যা ইতিমধ্যে সংলগ্ন নয়, এবং প্রথম এবং শেষ মেরুদণ্ডের শীর্ষগুলির মধ্যে। গোল্ডনার-হ্যারারি গ্রাফ একটি সমতলীয় গ্রাফের উদাহরণ প্রদান করে যার বইয়ের পুরুত্ব দুই নেইঃ এটি একটি সর্বাধিক সমতলীয় গ্রাফ, তাই সমতলীয়তা সংরক্ষণের সময় এটিতে কোনও প্রান্ত যুক্ত করা সম্ভব নয়, এবং এটির হ্যামিল্টনিয়ান চক্র নেই। হ্যামিল্টনিয়ান চক্রের এই বৈশিষ্ট্যের কারণে, যে গ্রাফগুলিতে দুই পৃষ্ঠার বইয়ের এম্বেডিং রয়েছে সেগুলি সাবহ্যামিল্টনিয়ান গ্রাফ নামেও পরিচিত। সমস্ত সমতলীয় গ্রাফ যার সর্বোচ্চ ডিগ্রি সর্বাধিক চারটি, তার বইয়ের পুরুত্ব সর্বাধিক দুটি। প্ল্যানার 3-গাছের বইয়ের পুরুত্ব সর্বাধিক তিনটি। আরও সাধারণভাবে, সমস্ত সমতলীয় গ্রাফের বইয়ের পুরুত্ব চার। 1986 সালে মিহালিস ইয়ানাকাকিস দাবি করেন যে, এমন কিছু সমতলীয় গ্রাফ রয়েছে যার বইয়ের পুরুত্ব ঠিক চারটি। যাইহোক, এই দাবির একটি বিস্তারিত প্রমাণ, যা পরবর্তী জার্নাল পেপারে ঘোষণা করা হয়েছিল, 2020 সাল পর্যন্ত জানা যায়নি, যখন বেকোস এট আল। ত্রি-প্রস্থ 4 সহ প্ল্যানার গ্রাফ উপস্থাপন করা হয়েছে যার জন্য যে কোনও বইয়ের এম্বেডিংয়ে চারটি পৃষ্ঠা প্রয়োজন। উপবিভাগের অধীনে আচরণ একটি গ্রাফের প্রতিটি প্রান্তকে দুটি প্রান্তে বিভক্ত করে, প্রতিটি প্রান্তের মধ্যে নতুন শীর্ষ যোগ করে, কখনও কখনও এর বইয়ের পুরুত্ব বাড়িয়ে তুলতে পারে। উদাহরণস্বরূপ, হীরার গ্রাফের বইয়ের পুরুত্ব এক (এটি বাইরের সমতলীয়) তবে এর উপবিভাগের বইয়ের পুরুত্ব দুই (এটি সমতলীয় এবং সাবহ্যামিলটোনিয়ান তবে বাইরের সমতলীয় নয়)। যাইহোক, এই উপবিভাগ প্রক্রিয়া কখনও কখনও উপবিভক্ত গ্রাফের বইয়ের পুরুত্ব উল্লেখযোগ্যভাবে হ্রাস করতে পারে। উদাহরণস্বরূপ, সম্পূর্ণ গ্রাফের বইয়ের পুরুত্ব তার শীর্ষগুলির সংখ্যার সাথে আনুপাতিক, তবে এর প্রতিটি প্রান্তকে দ্বি-প্রান্তের পথে বিভক্ত করলে একটি উপবিভাগ তৈরি হয় যার বইয়ের পুরুত্ব অনেক কম। এই ধরনের উদাহরণের অস্তিত্ব থাকা সত্ত্বেও, অনুমান করা হয় যে একটি মহকুমার বইয়ের পুরুত্ব মূল গ্রাফের তুলনায় খুব বেশি ছোট হতে পারে না। বিশেষত, তারা অনুমান করেছিলেন যে এমন একটি ফাংশন রয়েছে যে, প্রতিটি গ্রাফের জন্য এবং প্রতিটি প্রান্তকে দ্বি-প্রান্ত পথ দ্বারা প্রতিস্থাপিত করে গঠিত গ্রাফের জন্য, যদি বইয়ের পুরুত্ব হয় তবে বইয়ের পুরুত্ব সর্বাধিক হয়। তাদের অনুমান মিথ্যা প্রমাণিত হয়ঃ তারা এবং ত্রিভুজাকার টিলিংয়ের কার্টেসিয়ান পণ্য দ্বারা গঠিত গ্রাফগুলির সীমাহীন বইয়ের পুরুত্ব রয়েছে, তবে তাদের প্রান্তগুলিকে ছয়-প্রান্তের পথে বিভক্ত করলে তাদের বইয়ের পুরুত্ব কমে তিন হয়ে যায়। অন্যান্য গ্রাফ অপরিবর্তনীয়ের সাথে সম্পর্ক বইয়ের পুরুত্ব পুরুত্বের সাথে সম্পর্কিত, প্রদত্ত গ্রাফের প্রান্তগুলি আচ্ছাদন করার জন্য প্রয়োজনীয় সমতলীয় গ্রাফের সংখ্যা। একটি গ্রাফের পুরুত্ব থাকে যদি এটি সমতলে আঁকা যায় এবং এর প্রান্তগুলি এমনভাবে রঙিন হয় যে একে অপরের মতো একই রঙের প্রান্তগুলি অতিক্রম করে না। অনুরূপভাবে, একটি গ্রাফের বইয়ের পুরুত্ব থাকে যদি এটি একটি অর্ধ সমতলে আঁকা যায়, যার শীর্ষগুলি অর্ধ সমতলের সীমানায় থাকে, যার প্রান্তগুলি রঙিন হয় এবং একই রঙের দুটি প্রান্তের মধ্যে কোনও ক্রসিং থাকে না। বইয়ের পুরুত্বের এই গঠনে, প্রান্তের রঙগুলি বইয়ের এম্বেডিংয়ের পৃষ্ঠাগুলির সাথে মিলে যায়। যাইহোক, পুরুত্ব এবং বইয়ের পুরুত্ব একে অপরের থেকে খুব আলাদা হতে পারেঃ এমন গ্রাফ (সম্পূর্ণ গ্রাফের উপবিভাগ) রয়েছে যার পুরুত্ব দুই হওয়া সত্ত্বেও সীমাহীন বইয়ের পুরুত্ব রয়েছে। ত্রি-প্রস্থের গ্রাফগুলির বইয়ের পুরুত্ব সর্বাধিক এবং এই সীমাটি এর জন্য শক্ত। প্রান্তযুক্ত গ্রাফগুলির বইয়ের পুরুত্ব থাকে এবং বংশের গ্রাফগুলির বইয়ের পুরুত্ব থাকে। আরও সাধারণভাবে, প্রতিটি ছোটখাটো বন্ধ গ্রাফ পরিবারে বইয়ের পুরুত্ব সীমাবদ্ধ থাকে। অন্যদিকে, 1-সমতলীয় গ্রাফগুলি, যা অপ্রাপ্তবয়স্কদের অধীনে বন্ধ করা হয় না, সেগুলিরও বইয়ের পুরুত্ব সীমাবদ্ধ থাকে, তবে কিছু 1-সমতলীয় গ্রাফের বইয়ের পুরুত্ব কমপক্ষে চারটি থাকে। আবদ্ধ বইয়ের পুরুত্বের একটি গ্রাফের প্রতিটি অগভীর ছোট একটি বিরল গ্রাফ, যার প্রান্ত এবং শীর্ষের অনুপাত একটি ধ্রুবক দ্বারা আবদ্ধ যা শুধুমাত্র ছোটটির গভীরতা এবং বইয়ের পুরুত্বের উপর নির্ভর করে। অর্থাৎ, এর পরিভাষায়, আবদ্ধ বইয়ের পুরুত্বের গ্রাফগুলি সীমাবদ্ধ সম্প্রসারণ করেছে। যাইহোক, এমনকি সীমাবদ্ধ মাত্রার গ্রাফগুলি, সীমাবদ্ধ সম্প্রসারণের তুলনায় অনেক বেশি শক্তিশালী প্রয়োজনীয়তা, সীমাহীন বইয়ের পুরুত্ব থাকতে পারে। যেহেতু দুই বইয়ের পুরুত্বের গ্রাফগুলি সমতলীয় গ্রাফ, তাই তারা সমতলীয় বিভাজক উপপাদ্য মেনে চলেঃ তাদের বিভাজক রয়েছে, শীর্ষগুলির উপসেট রয়েছে যার অপসারণ গ্রাফটিকে সর্বাধিক শীর্ষ সহ টুকরো টুকরো করে বিভক্ত করে, বিভাজকে কেবল শীর্ষগুলি সহ। এখানে, গ্রাফের শীর্ষগুলির সংখ্যা বোঝায়। যাইহোক, বইয়ের পুরুত্ব তিন-এর গ্রাফ রয়েছে যার সাবলাইনার আকারের বিভাজক নেই। একটি বই এম্বেডিংয়ের একক পৃষ্ঠার মধ্যে প্রান্তগুলি স্ট্যাক ডেটা কাঠামোর মতো কিছু উপায়ে আচরণ করে। এটি একটি স্ট্যাকের উপর ধাক্কা এবং পপ ক্রিয়াকলাপের একটি নির্বিচারে ক্রম বিবেচনা করে এবং একটি গ্রাফ গঠন করে আনুষ্ঠানিক করা যেতে পারে যেখানে স্ট্যাক ক্রিয়াকলাপগুলি গ্রাফের শীর্ষগুলির সাথে সামঞ্জস্যপূর্ণ, একটি বইয়ের এম্বেডিংয়ের মেরুদণ্ড বরাবর ক্রম ক্রমে স্থাপন করা হয়। তারপর, যদি কেউ প্রতিটি পপ অপারেশন থেকে একটি প্রান্ত আঁকে যা স্ট্যাক থেকে একটি বস্তুকে পপ করে, পূর্ববর্তী পুশ অপারেশনে যা ধাক্কা দেয়, ফলস্বরূপ গ্রাফটিতে স্বয়ংক্রিয়ভাবে একটি পৃষ্ঠা এম্বেডিং থাকবে। এই কারণে, একটি গ্রাফের পৃষ্ঠা সংখ্যাকে তার স্ট্যাক নম্বরও বলা হয়। একইভাবে, কেউ একটি সারির তথ্য কাঠামোর এনকিউ এবং ডেক্যু ক্রিয়াকলাপের একটি নির্বিচারে ক্রম বিবেচনা করতে পারে এবং একটি গ্রাফ তৈরি করতে পারে যার শীর্ষে এই ক্রিয়াকলাপগুলি রয়েছে, প্রতিটি এনকিউ ক্রিয়াকলাপ এবং সংশ্লিষ্ট ডেকুর মধ্যে একটি প্রান্ত সহ একক পৃষ্ঠার মেরুদণ্ডের ক্রমানুসারে স্থাপন করা হয়েছে। তারপর, এই আলেখ্যে, প্রতিটি দুটি প্রান্ত মেরুদণ্ডের উপর বিচ্ছিন্ন ব্যবধানগুলি অতিক্রম করবে বা ঢেকে দেবে। উপমা হিসাবে, গবেষকরা একটি গ্রাফের সারি এম্বেডিংকে একটি টপোলজিকাল বইয়ে এম্বেডিং হিসাবে সংজ্ঞায়িত করেছেন যাতে প্রতিটি শীর্ষ মেরুদণ্ডের উপর থাকে, প্রতিটি প্রান্ত একটি একক পৃষ্ঠায় থাকে এবং একই পৃষ্ঠার প্রতিটি দুটি প্রান্ত মেরুদণ্ডের উপর বিচ্ছিন্ন ব্যবধানগুলি অতিক্রম করে বা আচ্ছাদন করে। একটি গ্রাফের সারি এম্বেড করার জন্য প্রয়োজনীয় ন্যূনতম সংখ্যক পৃষ্ঠাকে তার সারি সংখ্যা বলা হয়। গণনামূলক জটিলতা একটি গ্রাফের বইয়ের পুরুত্ব খুঁজে পাওয়া এনপি-হার্ড। এটি এই সত্য থেকে অনুসরণ করে যে সর্বাধিক সমতলীয় আলেখে হ্যামিল্টনিয়ান চক্র খুঁজে পাওয়া এনপি-সম্পূর্ণ। একটি সর্বাধিক সমতলীয় আলেখে, বইয়ের পুরুত্ব দুই হয় যদি এবং শুধুমাত্র একটি হ্যামিল্টনিয়ান চক্র বিদ্যমান থাকে। অতএব, প্রদত্ত সর্বাধিক সমতলীয় গ্রাফের বইয়ের পুরুত্ব দুই কিনা তা পরীক্ষা করাও এনপি-সম্পূর্ণ। যদি একটি এম্বেডিংয়ের মেরুদণ্ড বরাবর একটি গ্রাফের শীর্ষগুলির একটি ক্রম স্থির করা হয়, তবে একটি দুই পৃষ্ঠার এম্বেডিং (যদি এটি বিদ্যমান থাকে) রৈখিক সময়ে পাওয়া যেতে পারে, একটি গ্রাফের জন্য প্ল্যানারিটি পরীক্ষার উদাহরণ হিসাবে প্রদত্ত গ্রাফটি তাদের মেরুদণ্ডের ক্রমের শীর্ষগুলিকে সংযুক্ত করার একটি চক্রের সাথে বৃদ্ধি করে গঠিত হয়। দাবি করা হয়েছে যে একটি নির্দিষ্ট মেরুদণ্ডের ক্রমের সাথে তিন পৃষ্ঠার এম্বেডিং খুঁজে পাওয়া বহুপদী সময়েও সঞ্চালিত হতে পারে যদিও এই ফলাফলের তাঁর লেখায় অনেক বিবরণ বাদ দেওয়া হয়েছে। যাইহোক, যে গ্রাফগুলির জন্য চার বা ততোধিক পৃষ্ঠার প্রয়োজন হয়, ন্যূনতম সম্ভাব্য সংখ্যক পৃষ্ঠার সাথে একটি এম্বেডিং খুঁজে বের করার সমস্যাটি এনপি-হার্ড থাকে, বৃত্তের গ্রাফগুলি রঙ করার এনপি-হার্ড সমস্যার সমতুল্যতার মাধ্যমে, একটি বৃত্তের কর্ডগুলির ছেদ গ্রাফ। একটি গ্রাফ দেওয়া হয়েছে যার শীর্ষগুলির জন্য একটি নির্দিষ্ট মেরুদণ্ডের ক্রম সহ, একটি বৃত্তের চারপাশে একই ক্রমে এই শীর্ষগুলি আঁকা এবং রেখার অংশগুলির প্রান্তগুলি অঙ্কন করে প্রতিনিধিত্বকারী কর্ডগুলির একটি সংগ্রহ তৈরি করে। তারপরে কেউ একটি বৃত্তাকার গ্রাফ তৈরি করতে পারে যার মধ্যে এই চিত্রের কর্ডগুলি শীর্ষ হিসাবে এবং জোড়া কর্ডগুলিকে প্রান্ত হিসাবে অতিক্রম করে। বৃত্তের গ্রাফের একটি রঙ প্রান্তগুলিকে উপসেটগুলিতে বিভক্ত করার প্রতিনিধিত্ব করে যা একটি একক পৃষ্ঠায় অতিক্রম না করেই আঁকা যেতে পারে। অতএব, একটি সর্বোত্তম রঙ একটি সর্বোত্তম বই এম্বেডিংয়ের সমতুল্য। যেহেতু চার বা ততোধিক রঙের বৃত্তাকার গ্রাফ রঙ করা এনপি-হার্ড, এবং যেহেতু কোনও বই এম্বেডিং সমস্যা থেকে যে কোনও বৃত্তাকার গ্রাফ এইভাবে তৈরি করা যেতে পারে, তাই এটি অনুসরণ করে যে সর্বোত্তম বই এম্বেডিংও এনপি-হার্ড। দুই পৃষ্ঠার বইয়ের অঙ্কনের মেরুদণ্ডের উপর একটি নির্দিষ্ট শীর্ষক্রমের জন্য, যখন এই সংখ্যাটি শূন্য নয় তখন ক্রসিংয়ের সংখ্যা হ্রাস করাও এনপি-কঠিন। যদি মেরুদণ্ডের ক্রমটি অজানা থাকে তবে প্রান্তগুলিকে দুটি পৃষ্ঠায় বিভক্ত করা হয়, তবে এসপিকিউআর গাছের উপর ভিত্তি করে একটি অ্যালগরিদম দ্বারা রৈখিক সময়ে 2-পৃষ্ঠার এম্বেডিং (যদি এটি বিদ্যমান থাকে) খুঁজে পাওয়া সম্ভব। যাইহোক, মেরুদণ্ডের ক্রম বা প্রান্তের বিভাজন জানা না থাকলে 2-পৃষ্ঠার এম্বেডিং খুঁজে পাওয়া এনপি-সম্পূর্ণ। একটি গ্রাফের বুক ক্রসিং নম্বর খুঁজে পাওয়াও এনপি-হার্ড, কারণ 2-পৃষ্ঠার ক্রসিং নম্বরটি শূন্য কিনা তা পরীক্ষার বিশেষ ক্ষেত্রে এনপি-সম্পূর্ণতার কারণে। সীমাবদ্ধ সম্প্রসারণের ফলস্বরূপ, একটি বৃহত্তর গ্রাফের সাবগ্রাফ হিসাবে সীমাবদ্ধ আকারের একটি প্যাটার্ন গ্রাফ বিদ্যমান কিনা তা খুঁজে বের করার সাবগ্রাফ আইসোমরফিজম সমস্যাটি রৈখিক সময়ে সমাধান করা যেতে পারে যখন বৃহত্তর গ্রাফটি বইয়ের পুরুত্বকে সীমাবদ্ধ করে রাখে। প্যাটার্ন গ্রাফটি বৃহত্তর গ্রাফের একটি প্ররোচিত উপগ্রাফ কিনা, বা বৃহত্তর গ্রাফের সাথে এটির একটি গ্রাফ সমরূপতা আছে কিনা তা সনাক্ত করার ক্ষেত্রেও একই কথা প্রযোজ্য। একই কারণে, আবদ্ধ বইয়ের পুরুত্বের একটি গ্রাফ প্রথম ক্রম যুক্তির একটি প্রদত্ত সূত্র মেনে চলে কিনা তা পরীক্ষা করার সমস্যাটি স্থির-পরামিতি ট্র্যাক্টেবল। সমস্যাটিকে বুলিয়ান সন্তোষজনক সমস্যার একটি উদাহরণে রূপান্তরিত করে এবং ফলস্বরূপ সমস্যার জন্য একটি স্যাট সমাধানকারী প্রয়োগ করে সর্বোত্তম বই এম্বেডিং খুঁজে বের করার জন্য একটি সিস্টেম বর্ণনা করুন। তারা বলে যে তাদের সিস্টেমটি প্রায় 20 মিনিটের মধ্যে 400-ভার্টেক্স ম্যাক্সিমাল প্ল্যানার গ্রাফের জন্য একটি সর্বোত্তম এম্বেডিং খুঁজে পেতে সক্ষম। অ্যাপ্লিকেশন ত্রুটি-সহনশীল মাল্টিপ্রোসেসিং ত্রুটি-সহনশীল মাল্টিপ্রোসেসরের সংগঠনের জন্য ভিএলএসআই নকশায় একটি অ্যাপ্লিকেশন জড়িত বলে উদ্ধৃত বই এম্বেডিং অধ্যয়নের অন্যতম প্রধান অনুপ্রেরণা। এই লেখকদের দ্বারা বিকশিত ডিওজিনেস সিস্টেমে, একটি মাল্টিপ্রোসেসর সিস্টেমের সিপিইউগুলি একটি বইয়ের মেরুদণ্ডের সাথে সম্পর্কিত একটি যৌক্তিক ক্রমে সাজানো হয় (যদিও এই ক্রমটি এই সিস্টেমের শারীরিক বিন্যাসে একটি রেখা বরাবর স্থাপন করা আবশ্যক নয়)। এই প্রসেসরগুলিকে সংযুক্তকারী যোগাযোগ লিঙ্কগুলি "বান্ডিল"-এ গোষ্ঠীভুক্ত করা হয় যা একটি বইয়ের পৃষ্ঠাগুলির সাথে সামঞ্জস্যপূর্ণ এবং স্ট্যাকের মতো কাজ করেঃ প্রসেসরগুলির মধ্যে একটিকে একটি নতুন যোগাযোগ লিঙ্কের শুরুতে সংযুক্ত করা বান্ডিলের সমস্ত পূর্ববর্তী লিঙ্কগুলিকে উপরের দিকে ঠেলে দেয় এবং অন্য প্রসেসরকে একটি যোগাযোগ লিঙ্কের শেষে সংযুক্ত করে এটিকে বান্ডিলের নীচে একটির সাথে সংযুক্ত করে এবং অন্য সমস্তটিকে নিচে ফেলে দেয়। এই স্ট্যাক আচরণের কারণে, একটি একক বান্ডিল যোগাযোগ লিঙ্কগুলির একটি সেট পরিচালনা করতে পারে যা একটি বইয়ের এম্বেডিংয়ে একক পৃষ্ঠার প্রান্ত গঠন করে। এইভাবে লিঙ্কগুলি সংগঠিত করার মাধ্যমে, বিভিন্ন ধরনের নেটওয়ার্ক টপোলজি প্রয়োগ করা যেতে পারে, যতক্ষণ পর্যন্ত নেটওয়ার্কটি বাস্তবায়নের জন্য পর্যাপ্ত অ-ত্রুটিপূর্ণ প্রসেসর থাকে ততক্ষণ পর্যন্ত প্রসেসরগুলি ত্রুটিপূর্ণ হয়ে যায়। এই ব্যবস্থার মাধ্যমে যে নেটওয়ার্ক টপোলজিগুলি প্রয়োগ করা যেতে পারে সেগুলির বইয়ের পুরুত্ব সর্বাধিক বান্ডিলের সংখ্যার সমান। বুক এম্বেডিং একটি সার্কিটের স্তরগুলিতে ভিএলএসআই উপাদানগুলিকে সংযুক্ত করার জন্য তারের স্থাপনার মডেল তৈরি করতেও ব্যবহার করা যেতে পারে। স্ট্যাক বাছাই স্ট্যাক ব্যবহার করে বিন্যাস বাছাই করার উদ্বেগের দ্বারা উদ্ধৃত আরেকটি অ্যাপ্লিকেশন। এর একটি প্রভাবশালী ফলাফল দেখায় যে একটি সিস্টেম যা একটি ডেটা স্ট্রিমকে একটি স্ট্যাকের উপর আগত উপাদানগুলিকে ধাক্কা দিয়ে প্রক্রিয়া করে এবং তারপরে, যথাযথভাবে নির্বাচিত সময়ে, স্ট্যাক থেকে একটি আউটপুট স্ট্রিমের উপর পপ করে ডেটা সাজাতে পারে যদি এবং কেবলমাত্র যদি তার প্রাথমিক ক্রমটি দ্বারা বর্ণনা করা হয়। তারপর থেকে, স্ট্যাক এবং সারিগুলির আরও সাধারণ সিস্টেম দ্বারা ডেটা স্ট্রিমগুলি বাছাই করার অনুরূপ সমস্যাগুলির উপর অনেক কাজ করা হয়েছে। দ্বারা বিবেচিত সিস্টেমে, একটি ইনপুট ডেটা স্ট্রিম থেকে প্রতিটি উপাদানকে অবশ্যই বেশ কয়েকটি স্ট্যাকের মধ্যে একটিতে ঠেলে দিতে হবে। তারপরে, একবার সমস্ত ডেটা এইভাবে ধাক্কা দেওয়া হয়ে গেলে, আইটেমগুলি এই স্ট্যাকগুলি থেকে (উপযুক্ত ক্রমে) একটি আউটপুট প্রবাহে পপ করা হয়। যেমন চুং এবং অন্যান্য। লক্ষ্য করুন, একটি প্রদত্ত ক্রমাঙ্কন এই পদ্ধতি দ্বারা সাজানো যেতে পারে যদি এবং শুধুমাত্র যদি ক্রমাঙ্কন থেকে উদ্ভূত একটি নির্দিষ্ট গ্রাফের মেরুদণ্ড বরাবর একটি নির্দিষ্ট নির্দিষ্ট ক্রমে শীর্ষগুলির সাথে একটি বই এম্বেড করা থাকে এবং বেশ কয়েকটি পৃষ্ঠা থাকে যা স্ট্যাকের সংখ্যার সর্বাধিক সমান। ট্রাফিক নিয়ন্ত্রণ যেমন বর্ণনা করা হয়েছে, একটি বই এম্বেডিং একটি নিয়ন্ত্রিত সংযোগস্থলে ট্রাফিক সিগন্যালের পর্যায়গুলি বর্ণনা করতে ব্যবহার করা যেতে পারে। একটি সংযোগস্থলে, ট্রাফিকের আগত এবং বহির্গামী লেনগুলি (পথচারীদের ক্রসওয়াক এবং সাইকেল লেনের প্রান্তের পাশাপাশি মোটর যানবাহনের লেন সহ) একটি গ্রাফের শীর্ষ হিসাবে প্রতিনিধিত্ব করা যেতে পারে, যা একটি বইয়ের মেরুদণ্ডের উপর স্থাপন করা হয় যা তাদের ঘড়ির কাঁটার দিকে ক্রমানুসারে সংযুক্ত থাকে। একটি আগত লেন থেকে একটি বহির্গামী লেনে যাওয়ার জন্য ট্র্যাফিক দ্বারা নেওয়া ছেদগুলির মধ্য দিয়ে যাওয়া পথগুলিকে একটি অনির্দিষ্ট গ্রাফের প্রান্ত হিসাবে উপস্থাপন করা যেতে পারে। উদাহরণস্বরূপ, এই গ্রাফের একটি প্রান্ত থাকতে পারে একটি আগত থেকে একটি বহির্গামী লেন পর্যন্ত যা উভয়ই রাস্তার একই অংশের অন্তর্গত, যা সেই অংশ থেকে সেই অংশে ফিরে ইউ-টার্নের প্রতিনিধিত্ব করে, শুধুমাত্র যদি জংশনে ইউ-টার্নের অনুমতি দেওয়া হয়। এই প্রান্তগুলির একটি প্রদত্ত উপসেটের জন্য, উপসেটটি এমন পথের একটি সংগ্রহের প্রতিনিধিত্ব করে যা একে অপরের হস্তক্ষেপ ছাড়াই অতিক্রম করা যেতে পারে যদি এবং কেবলমাত্র যদি উপসেটটিতে কোনও জোড়া প্রান্ত অন্তর্ভুক্ত না থাকে যা দুটি প্রান্তকে একটি বইয়ের এম্বেডিংয়ের একক পৃষ্ঠায় স্থাপন করা হলে অতিক্রম করবে। সুতরাং, এই গ্রাফের একটি বই এম্বেডিং পথগুলিকে অ-হস্তক্ষেপকারী উপসেটগুলিতে বিভক্ত করার বর্ণনা দেয় এবং এই গ্রাফের বইয়ের পুরুত্ব (মেরুদণ্ডের উপর স্থির এম্বেডিং সহ) একটি সংকেত সময়সূচির জন্য প্রয়োজনীয় ন্যূনতম সংখ্যক স্বতন্ত্র পর্যায় দেয় যা জংশনের মধ্য দিয়ে সমস্ত সম্ভাব্য ট্র্যাফিক পথ অন্তর্ভুক্ত করে। গ্রাফ অঙ্কন বই এম্বেডিং প্রায়শই নেটওয়ার্ক ডেটার ভিজ্যুয়ালাইজেশনে প্রয়োগ করা হয়েছে। গ্রাফ অঙ্কনের দুটি আদর্শ বিন্যাস, আর্ক ডায়াগ্রাম এবং বৃত্তাকার বিন্যাস, বই এম্বেডিং হিসাবে দেখা যেতে পারে এবং বই এম্বেডিং ক্লাস্টারযুক্ত বিন্যাস, একযোগে এম্বেডিং এবং ত্রিমাত্রিক গ্রাফ অঙ্কন নির্মাণেও প্রয়োগ করা হয়েছে। একটি চাপ রেখাচিত্র বা রৈখিক এম্বেডিং একটি রেখা বরাবর একটি গ্রাফের শীর্ষস্থান স্থাপন করে এবং এই রেখার উপরে বা নীচে অর্ধবৃত্তাকার হিসাবে গ্রাফের প্রান্তগুলি আঁকে, কখনও কখনও রেখার অংশগুলিতে প্রান্তগুলি আঁকার অনুমতি দেয়। এই অঙ্কন শৈলীটি একটি পৃষ্ঠা (যদি সমস্ত অর্ধবৃত্ত রেখার উপরে থাকে) বা দুটি পৃষ্ঠা (যদি রেখার উভয় দিক ব্যবহার করা হয়) সহ একটি বইয়ের এম্বেডিংয়ের সাথে মিলে যায় এবং মূলত গ্রাফের ক্রসিং সংখ্যা অধ্যয়নের উপায় হিসাবে চালু করা হয়েছিল। দুই পৃষ্ঠার বইয়ের এম্বেডিং নেই এমন প্ল্যানার গ্রাফগুলিও একইভাবে আঁকা যেতে পারে, যাতে তাদের প্রান্তগুলি রেখার উপরে এবং নীচে একাধিক অর্ধবৃত্ত দ্বারা প্রতিনিধিত্ব করা যায়। এই ধরনের অঙ্কন সাধারণ সংজ্ঞা দ্বারা এম্বেড করা কোনও বই নয়, তবে এটিকে টপোলজিকাল বুক এম্বেডিং বলা হয়। প্রতিটি প্ল্যানার গ্রাফের জন্য, এমন একটি এম্বেডিং খুঁজে পাওয়া সর্বদা সম্ভব যেখানে প্রতিটি প্রান্ত সর্বাধিক একবার মেরুদণ্ড অতিক্রম করে। আরেকটি অঙ্কন শৈলীতে, বৃত্তাকার বিন্যাস, একটি গ্রাফের শীর্ষগুলি একটি বৃত্তের উপর স্থাপন করা হয় এবং প্রান্তগুলি বৃত্তের ভিতরে বা বাইরে আঁকা হয়। আবার, বৃত্তের মধ্যে প্রান্তগুলির স্থাপন (উদাহরণস্বরূপ সরলরেখার অংশ হিসাবে) এক পৃষ্ঠার বইয়ের অঙ্কনের সাথে মিলে যায়, যখন বৃত্তের ভিতরে এবং বাইরে উভয় স্থানই দুই পৃষ্ঠার বইয়ের অঙ্কনের সাথে মিলে যায়। উভয় শৈলীর এক পৃষ্ঠার অঙ্কনের জন্য, অঙ্কনের চাক্ষুষ বিশৃঙ্খলা হ্রাস করার উপায় হিসাবে ক্রসিংয়ের সংখ্যা ছোট রাখা গুরুত্বপূর্ণ। ক্রসিংয়ের সংখ্যা হ্রাস করা এনপি-সম্পূর্ণ, তবে শীর্ষগুলির সংখ্যা কোথায় তার আনুমানিক অনুপাতের সাথে আনুমানিক হতে পারে। প্রদত্ত গ্রাফের সাইক্লোম্যাটিক সংখ্যা দ্বারা বা ক্রসিং নম্বর এবং গ্রাফের ত্রি-প্রস্থের সংমিশ্রণ দ্বারা প্যারামিটারাইজ করা হলে এক-পৃষ্ঠা বা দুই-পৃষ্ঠা ক্রসিং নম্বরকে ন্যূনতম করা নির্দিষ্ট-পরামিতি ট্র্যাক্টেবল। ক্রসিং জটিলতা হ্রাস করার জন্য অনুসন্ধানমূলক পদ্ধতিও তৈরি করা হয়েছে, যেমন। একটি সতর্ক ভার্টেক্স সন্নিবেশ ক্রমে এবং স্থানীয় অপ্টিমাইজেশনে। পৃষ্ঠাগুলিতে প্রান্তগুলির একটি নির্দিষ্ট বিভাজন সহ দুই পৃষ্ঠার বইয়ের এম্বেডিংকে ক্লাস্টার্ড প্ল্যানারিটির একটি রূপ হিসাবে ব্যাখ্যা করা যেতে পারে, যেখানে প্রদত্ত গ্রাফটি এমনভাবে আঁকতে হবে যাতে গ্রাফের অংশগুলি (প্রান্তের দুটি উপসেট) ড্রয়িংয়ে এমনভাবে স্থাপন করা হয় যা তাদের ক্লাস্টারিংকে প্রতিফলিত করে। দুই পৃষ্ঠার বই এম্বেডিং গ্রাফের একযোগে এম্বেডিং খুঁজে বের করার জন্যও ব্যবহার করা হয়েছে, যেখানে একই শীর্ষে দুটি গ্রাফ দেওয়া হয়েছে এবং উভয় গ্রাফ সোজা প্রান্তের সাথে সমতলভাবে আঁকা শীর্ষগুলির জন্য একটি স্থান খুঁজে বের করতে হবে। গ্রাফের ত্রিমাত্রিক অঙ্কন তৈরি করতে দুই পৃষ্ঠার বেশি বইয়ের এম্বেডিংও ব্যবহার করা হয়েছে। বিশেষত, বই এম্বেডিংয়ের জন্য একটি নির্মাণ ব্যবহার করা হয়েছে যা প্রতিটি পৃষ্ঠার মধ্যে প্রতিটি শীর্ষের ডিগ্রি কম রাখে, কম ভলিউমের ত্রিমাত্রিক গ্রিডে গ্রাফ এম্বেড করার পদ্ধতির অংশ হিসাবে। আর. এন. এ ভাঁজ করা আর. এন. এ অণুগুলি কীভাবে তাদের কাঠামো গঠনের জন্য ভাঁজ হয় তার অধ্যয়নে, নিউক্লিক অ্যাসিড গৌণ কাঠামোর আদর্শ রূপটিকে রেখাচিত্রিকভাবে ঘাঁটির একটি শৃঙ্খল (আর. এন. এ ক্রম নিজেই) হিসাবে বর্ণনা করা যেতে পারে, যা একটি রেখা বরাবর আঁকা হয়, কাঠামোর বেসপেয়ারগুলি বর্ণনা করে লাইনের উপরে চাপের সংগ্রহের সাথে। অর্থাৎ, যদিও এই কাঠামোগুলির প্রকৃতপক্ষে একটি জটিল ত্রিমাত্রিক আকৃতি রয়েছে, তাদের সংযোগ (যখন একটি গৌণ কাঠামো বিদ্যমান থাকে) আরও বিমূর্ত কাঠামো দ্বারা বর্ণনা করা যেতে পারে, একটি এক পৃষ্ঠার বই এম্বেডিং। তবে, সমস্ত আর. এন. এ ভাঁজ এই সহজ পদ্ধতিতে আচরণ করে না। কিছু নির্দিষ্ট আর. এন. এ সিউডোকনটের জন্য একটি তথাকথিত "দ্বি-গৌণ কাঠামো" প্রস্তাব করা হয়েছে যা দুই পৃষ্ঠার বইয়ের এম্বেডিংয়ের রূপ নেয়ঃ আর. এন. এ ক্রমটি আবার একটি রেখা বরাবর আঁকা হয়, তবে বেসপেয়ারগুলি এই রেখার উপরে এবং নীচে উভয়ই চাপ হিসাবে আঁকা হয়। একটি দ্বি-গৌণ কাঠামো গঠনের জন্য, একটি গ্রাফের সর্বাধিক তিনটি ডিগ্রি থাকতে হবেঃ প্রতিটি বেস কেবলমাত্র ডায়াগ্রামের একটি আর্কে অংশ নিতে পারে, বেস সিকোয়েন্সে তার প্রতিবেশীদের সাথে দুটি লিঙ্ক ছাড়াও। এই গঠনের সুবিধাগুলির মধ্যে রয়েছে যে এটি এমন কাঠামোগুলিকে বাদ দেয় যা আসলে মহাকাশে গাঁটছড়া বাঁধে এবং এটি সর্বাধিক পরিচিত আরএনএ সিউডোকনটের সাথে মেলে। যেহেতু এই প্রয়োগের জন্য মেরুদণ্ডের ক্রম আগে থেকে জানা থাকে, তাই প্রদত্ত বেসপেয়ারিংয়ের জন্য দ্বি-মাধ্যমিক কাঠামোর অস্তিত্বের জন্য পরীক্ষা করা সোজা। সামঞ্জস্যপূর্ণ উপায়ে দুটি পৃষ্ঠায় প্রান্ত বরাদ্দ করার সমস্যাটি হয় 2-সন্তোষজনকতার উদাহরণ হিসাবে তৈরি করা যেতে পারে, অথবা বৃত্ত গ্রাফের দ্বিদলীয়তা পরীক্ষা করার সমস্যা হিসাবে তৈরি করা যেতে পারে যার শীর্ষগুলি বেসপেয়ার এবং যার প্রান্তগুলি বেসপেয়ারের মধ্যে ক্রসিং বর্ণনা করে। বিকল্পভাবে এবং আরও দক্ষতার সাথে, যেমন দেখানো হয়েছে, একটি দ্বি-গৌণ কাঠামো বিদ্যমান থাকে যদি এবং শুধুমাত্র যদি ইনপুটের চিত্র গ্রাফ (একটি গ্রাফ যা ঘাঁটিগুলিকে তাদের ক্রম ক্রমে একটি চক্রে সংযুক্ত করে এবং প্রদত্ত বেসপেয়ারগুলিকে প্রান্ত হিসাবে যুক্ত করে গঠিত হয়) একটি সমতলীয় গ্রাফ হয়। এই বৈশিষ্ট্যায়ন দ্বিমাত্রিক কাঠামোকে সমতলীয় পরীক্ষার উদাহরণ হিসাবে রৈখিক সময়ে স্বীকৃতি দেওয়ার অনুমতি দেয়। আরএনএ গৌণ কাঠামোর তুলনায় নির্দিষ্ট সমস্যার এনপি-কঠোরতার প্রমাণের অংশ হিসাবে গৌণ কাঠামো এবং বই এম্বেডিংয়ের মধ্যে সংযোগ ব্যবহার করা হয়েছে। এবং যদি একটি আর. এন. এ কাঠামো দ্বি-মাধ্যমিকের পরিবর্তে তৃতীয় হয় (অর্থাৎ, যদি এটির চিত্রটিতে দুই পৃষ্ঠার বেশি প্রয়োজন হয়), তবে পৃষ্ঠা সংখ্যা নির্ধারণ করা আবার এন. পি-হার্ড। গণনামূলক জটিলতা তত্ত্ব নির্দেশিত গ্রাফগুলিতে পৌঁছানোর সমস্যার গণনামূলক জটিলতা তত্ত্ব অধ্যয়ন করতে বই এম্বেডিং ব্যবহার করে। তারা যেমন পর্যবেক্ষণ করেছেন, দুই পৃষ্ঠার নির্দেশিত গ্রাফের পৌঁছনোযোগ্যতা দ্ব্যর্থহীন লগারিদমিক স্পেসে সমাধান করা যেতে পারে (এনালগ, লগারিদমিক স্পেস জটিলতার জন্য, দ্ব্যর্থহীন বহুপদী-সময়ের সমস্যার ক্লাস ইউপির)। যাইহোক, তিন পৃষ্ঠার নির্দেশিত গ্রাফের পৌঁছানোর জন্য অনির্ধারিত লগারিদমিক স্থানের সম্পূর্ণ শক্তি প্রয়োজন। সুতরাং, বই এম্বেডিং এই দুটি জটিলতা শ্রেণীর মধ্যে পার্থক্যের সাথে ঘনিষ্ঠভাবে সংযুক্ত বলে মনে হয়। ধ্রুবক পৃষ্ঠা সংখ্যা সহ এক্সপ্যান্ডার গ্রাফের অস্তিত্ব প্রমাণ করার মূল পদক্ষেপ যে এক-টেপ অ-নির্ধারক টুরিং মেশিন দ্বারা দুই-টেপ অ-নির্ধারক টুরিং মেশিনের কোনও সাবকোয়াড্রাটিক-টাইম সিমুলেশন নেই। গণিতের অন্যান্য ক্ষেত্রগুলি বিমূর্ত বীজগণিতে বইয়ের পুরুত্বের প্রয়োগগুলি অধ্যয়ন করে, প্রতিটি শূন্য বিভাজকের জন্য একটি শীর্ষ এবং প্রতিটি জোড়া মানের জন্য একটি প্রান্ত তৈরি করে একটি সীমাবদ্ধ স্থানীয় বলয়ের শূন্য ভাজক থেকে সংজ্ঞায়িত গ্রাফ ব্যবহার করে যার গুণফল শূন্য। একটি বহু-কাগজের ক্রমে, ডাইনিকভ নট এবং লিঙ্কগুলির টপোলজিকাল বইয়ের এম্বেডিং অধ্যয়ন করেছেন, যা দেখায় যে এই এম্বেডিংগুলি প্রতীকগুলির একটি সমন্বিত ক্রম দ্বারা বর্ণনা করা যেতে পারে এবং দুটি লিঙ্কের টপোলজিকাল সমতুল্যতা এম্বেডিংয়ে স্থানীয় পরিবর্তনের ক্রম দ্বারা প্রদর্শিত হতে পারে। তথ্যসূত্র টপোলজিক্যাল গ্রাফ তত্ত্ব