گراف ۱-مسطح

یک ترسیم ۱-مسطح از
در نظریه توپولوژیک گراف، یک گراف ۱-مسطح گرافی است که می‌توان آن را طوری در صفحه اقلیدسی ترسیم کرد که هر یال حداکثر یک تقاطع با یال‌های دیگر داشته باشد. به عبارت دیگر، هیچ یالی با دو یال دیگر متقاطع نباشد. به چنین ترسیمی هم یک ترسیم ۱-مسطح از گراف می‌گویند (گرافی که حداقل یک ترسیم ۱-مسطح داشته باشد، گراف ۱-مسطح نامیده می‌شود).
رنگ‌آمیزی
گرهارد رینگل (۱۹۹۵) اولین کسی بود که به مطالعه گراف‌های ۱-مسطح پرداخت. او نشان داد که این گراف‌ها را می‌توان با حداکثر ۷ رنگ رنگ‌آمیزی کرد. بعدا مشخص شد که تعداد دقیق رنگ‌های مورد نیاز برای رنگ‌آمیزی این گراف‌ها در بدترین حالت، عدد ۶ است. گراف کامل K ۶ نمونه‌ای است که نشان می‌دهد تعداد ۶ رنگ در بعضی حالات مورد نیاز است. با این حال، اثبات اینکه ۶ رنگ همیشه کافی خواهد بود، پیچیده‌تر از اینهاست.
رنگ‌آمیزی رئوس و وجوه گراف منشور مثلثی، نیازمند ۶ رنگ است
انگیزه رینگل این بود که بتواند نوعی از رنگ‌آمیزی کامل را برای گراف‌های مسطح حل کند، که در آن تمام رئوس و وجوه یک گراف مسطح را همزمان طوری رنگ می‌کنیم که هیج دو راس مجاوری همرنگ نبوده، هیج دو وجه مجاوری همرنگ نبوده، و هیچ راس و وجهی که مجاور هستند همرنگ نباشند. این کار به وضوح توسط ۸ رنگ قابل انجام است، کافی است قضیه چهاررنگ را بر روی گراف داده شده و گراف همزاد (dual) آن با دو مجموعه مجزا از ۴ رنگ بطور مجزا اعمال کنیم. با این حال، برای دستیابی به تعداد کمتری از رنگ‌ها می‌توان یک گراف کمکی تشکیل داد که یک راس به ازای هر راس یا وجه گراف مسطح داده شده دارد، و دو راس این گراف کمکی مجاور هستند اگر و فقط اگر دو راس/وجه متناظر آن‌ها در گراف اصلی مجاور باشند. یک رنگ‌آمیزی راسی این گراف کمکی معادل یک رنگ‌آمیزی راسی-وجهی گراف مسطح اصلی است. این گراف کمکی یک گراف ۱-مسطح است، و از اینجا بود که مسئله رنگ‌آمیزی راسی-وجهی رینگل منجر به رنگ‌آمیزی راسی گراف ۱-مسطح شد، و اکنون می‌دانیم که هر دوی این مسائل با ۶ رنگ قابل حل هستند. گرچه گراف کامل K ۶ را نمی‌توان بعنوان یک گراف کمکی تشکیل داد، اما برای نمونه اگر گراف مسطح منشور مثلثی را بخواهیم رنگ‌آمیزی وجهی-راسی کنیم، یازده راس و وجه آن به ۶ رنگ نیاز دارند، چون به هیچ سه تایی از آن‌ها نمی‌توان یک رنگ اختصاص داد.
تراکم یال‌ها
هر گراف ۱-مسطح با n راس حداکثر ۴n − ۸ یال دارد. قوی‌تر اینکه، هر ترسیم ۱-مسطح حداکثر n − ۲ تقاطع دارد؛ حذف یک یال از هر زوج یال‌های متقاطع، یک گراف مسطح را باقی می‌گذارد، که می‌تواند حداکثر ۳n − ۶ یال داشته باشد، که بلافاصله نتیجه می‌دهد گراف ۱-مسطح اصلی حداکثر می‌توانست ۴n − ۸ یال داشته باشد. با این حال، بر خلاف گراف‌های مسطح (که تمام گراف‌های مسطح بیشینه روی یک مجموعه از رئوس مشخص، تعداد یکسانی از یال‌ها دارند)، گراف‌های ۱-مسطح بیشینه‌ای (که هیچ یال جدیدی با حفظ ۱-مسطح بودن نمی‌توان به آن‌ها اضافه کرد) وجود دارند که تعداد یال بسیار کمتری از ۴n − ۸ دارند. محدودیت ۴n − ۸ برای حداکثر تعداد یال‌ها در یک گراف ۱-مسطح می‌تواند نشان دهد که گراف کامل K ۷ یک گراف ۱-مسطح نیست، چون دارای ۷ راس و ۲۱ یال بوده و ۴n − ۸ = ۲۰ < ۲۱.
یک گراف ۱-مسطح را یک گراف ۱-مسطح بهینه می‌گویند اگر دقیقا ۴n − ۸ یال داشته باشد، که حداکثر تعداد ممکن است. در یک زیرگراف از یک گراف ۱-مسطح بهینه، یال‌های بدون تقاطع لزوما تشکیل یک گراف مربعی می‌دهند (یک گراف چندوجهی که هر وجه آن یک چهارضلعی است). از این طریق هر گراف مربعی با اضافه کردن دو قطر به هر یک از وجوه چهارضلعی‌اش یک گراف ۱-مسطح بهینه را تولید می‌کند. در نتیجه هر گراف ۱-مسطح بهینه یک گراف اویلری است (تمام رئوسش درجه زوج دارند)، که حداقل درجه رئوس در آن ۶ است. همچنین هر گراف ۱-مسطح بهینه حداقل ۸ راس با درجه دقیقا ۶ دارد. به علاوه، هر گراف ۱-مسطح بهینه یک گراف ۴-راس-همبند بوده، و هر برش ۴-راسی در چنین گرافی یک حلقه جداکننده در گراف مربعی زیرین است.
گراف‌هایی که ترسیم ۱-مسطح مستقیم دارند (ترسیمی که هر یال یک خط مستقیم است با حداکثر یک تقاطع) محدوده تنگ‌تری برای تعداد یال‌ها دارند؛ این گراف‌ها حداکثر ۴n − ۹ یال می‌توانند داشته باشند.
گراف‌های چندبخشی کامل
یک ترسیم ۱-مسطح از گراف توران K ۲,۲,۲,۲
زیرمجموعه‌ای از گراف‌های ۱-مسطح که گراف کامل، گراف دوبخشی کامل یا بطور کلی گراف چندبخشی کامل هستند در دسته‌های شناخته‌شده‌ای قرار دارند. هر گراف دوبخشی کامل در شکل K ۲،n یک گراف ۱-مسطح است، همینطور هر گراف سه‌بخشی کامل به شکل K ۱،۱،n . غیر از این مجموعه‌های نامتناهی از نمونه‌ها، تنها گراف‌های چندبخشی کامل ۱-مسطح این گراف‌ها:
K ۶ , K ۱،۱،۱،۶ , K ۱،۱،۲،۳ , K ۲،۲،۲،۲ , K ۱،۱،۱،۲،۲
و زیرگراف‌های آن‌ها هستند.
گراف‌های کمینه غیر-۱-مسطح چندبخشی کامل این‌ها هستند:
K ۳،۷ , K ۴،۵ , K ۱،۳،۴ , K ۲،۳،۳ , K ۱،۱،۱،۱،۳
به عنوان مثال، گراف دوبخشی کامل K ۳،۶ گراف ۱-مسطح است چون زیرگرافی از K ۱،۱،۱،۶ است، اما K ۳،۷ گراف ۱-مسطح نیست.