২০০৪ সালে, দুজন গণিতজ্ঞ একটি শক্তিশালী ধরনের স্যান্ডউইচের অনুমান করেছিলেন যাতে একটি বিশ্লেষণ করা কঠিন গ্রাফের বৈশিষ্ট্যগুলো বোঝা যায়। তাদের লক্ষ্য ছিল এটিকে দুটি সহজ গ্রাফের মাঝপথে রাখা যাতে এর মূল বৈশিষ্ট্যগুলো প্রদর্শন করা যায় এবং দুটি যাদৃচ্ছিক প্রক্রিয়াকে আরও গভীরভাবে সংযুক্ত করা যায়। এই ধারণাটিকে কানাডার ওয়াটারলো বিশ্ববিদ্যালয়ের গণিতজ্ঞ পু গাও (Pu Gao) "সুন্দর" বলে বর্ণনা করেছিলেন। ১৯৫০-এর দশকের শেষে, বেল ল্যাবসের এডগার গিলবার্ট (Edgar Gilbert) সিক্কা উछালে শীর্ষবিন্দু সংযুক্ত করে যাদৃচ্ছিক দ্বিপদ গ্রাফ তৈরি করেছিলেন। নিয়মিত গ্রাফে, যেখানে সব শীর্ষবিন্দুর সমান সংখ্যক প্রান্ত থাকে, বাস্তব জগতের নেটওয়ার্ক মডেল করার জন্য আরও সঠিক কিন্তু বিশ্লেষণ করা কঠিন। ২০০০-এর দশকের শুরুতে, মাইক্রোসফট রিসার্চের জिओং হান কিম (Jeong Han Kim) এবং ইউসি স্যান ডিয়েগোর ভ্যান হা ভু (Van Ha Vu) নিয়মিত গ্রাফকে দ্বিপদ গ্রাফ দিয়ে অনুমান করার জন্য একটি গ্রাফ স্যান্ডউইচ তৈরি করেছিলেন, যাতে দ্বিপদ গ্রাফের ফলাফল নিয়মিত গ্রাফে প্রযোজ্য হয়।