نشاندن گراف

اصطلاحات

اگر گراف G در یک فضای بستهٔ ∑ نشانده شود، مکمل اجتماع نقاط و کمان‌های متصل به رئوس و لبه‌های G جزئی از ناحیه‌ها می‌باشد. یک نشاندن دوسلولی یا نگاشت، نوعی از نشاندن به طوری است که هر نما در یک فضای باز همریخت می‌باشد. یک نشاندن دوسلولی بسته نوعی از نشاندن است که در آن بستار هر نما با فضای بسته همریخت می‌باشد.
نوع هر گراف حداقل عدد صحیحی است که گراف می‌تواند درون یک سطح نوع n نشانده شود. به‌طور خاص یک گراف مسطح داری نوع صفر می‌باشد زیرا می‌تواند بر روی یک کره بدون تقاطع کشیده شود. گراف غیر جهت‌دار از نوع حداقل عدد صحیح n می‌باشد که گراف می‌تواند در یک سطح غیر جهت‌دار نوع n نشانده شود.
گراف نوع اویلر گرافیست از حداقل عدد صحیح n به طوری که گراف می‌تواند در یک سطح جهت دار نوع n/2 یا در یک سطح غیر جهت‌دار نوع n نشانده شود. یک گراف از نوع ساده جهت‌دار می‌باشد اگر عدد اویلر آن کوچکتر از عدد غیر جهت دار آن باشد.
نوع حداکثر گراف بزرگترین عدد صحیح n است که گراف می‌تواند به صورت دو سلولی در یک سطح جهت‌دار نوع n نشانده شود.

نشاندن ترکیبی

یک گراف نشانده شده به صورت یکتا ترتیب چرخه‌ای لبه‌های مجاور به رئوس مشابه را توصیف می‌کند. مجموعهٔ تمام این مرتبه‌های چرخه‌ای سیستم چرخش نامیده می‌شود. مشاندن با سیستم چرخش مشابه یکسان در نظر گرفته می‌شود و کلاس یکسان مرتبط با نشاندن‌ها، نشاندن ترکیبی نامیده می‌شود (همان‌طور که از نام نشاندن مکانی استنباط می‌شود به تعریف قبلی نقاط و منحنی‌ها اطلاق می‌شود). گاهی اوقات سیستم چرخش، نشاندن ترکیبی نامیده می‌شود.
یک گراف نشانده شده همچنین مرتبه چرخه‌ای طبیعی لبه‌ها را نیز توصیف می‌کند که مرزهای نماهای نشاندن را تشکیل می‌دهد.
با این حال مدیریت این مراتب مبتنی بر نما هموار و آسان نمی‌باشد، زیرا در یعضی موارد بعضی از لبه‌ها ممکن است دو بار در راستای مرز نما عبور کنند. به‌طور مثال این موضوع برای نشاندن درخت‌ها همیشه روی می‌دهد که دارای یک نمای منفرد می‌باشد. برای چیره شدن بر این مشکل ترکیبی، یک فرد ممکن است فرض کند که هر لبه به صورت طولی در دو "نصف لبه" یا در دو "سمت" "تجزیه" بشوند. تحت این شرایط در عبور از تمام مرزهای نماها، هر نصفه لبه تنها یکبار عبور می‌کند و هر دو نصفه لبه از لبهٔ مشابه در جهت عکس عبور می‌کند.

پیچیدگی محاسباتی

مسئلهٔ کشف نوع گراف نوعی از مسائل ان‌پی سخت می‌باشد (مسئله تعیین اینکه آیا یک گراف n راسی نوع g می‌باشد یا خیر از نوع ان‌پی کامل می‌باشد)
در همین زمان مسئلهٔ نوع گراف، از نوع پارامترهای ثابت رام شونده می‌باشد مثل الگوریتم‌هایی با زمان چند جمله‌ای که در چک کردن اینکه آیا یک گراف می‌تواند در یک فضا با نوع ثابت همچون کشف نشاندن شناخته‌شده می‌باشد.
اولین پیشرفت مهم مرتبط با این موضوع در سال ۱۹۷۹ در حالی روی داد که الگوریتم‌های با پیچیدگی زمانی O(nO(g)) به صورت مستقل در ACM Symposium on Theory of Computing ارائه می‌شدند. یکی از آن‌ها توسط (فیلوتی I.Filotti) و (میلر G.L.Miller) و دیگری توسط (جان ریف John Reif) ارائه شد. رویکردهای آن‌ها کاملاً با یکدیگر متفاوت بود اما بر اساس پیشنهاد کمیته برنامه‌ریزی آن‌ها یک مقالهٔ اشتراکی ارائه دادند.
در سال ۱۹۹۹ گزارش شد که مورد نوع ثابت می‌تواند در زمان خطی در فضای گراف و زمان دو برابر نمایی در نوع گراف حل شود.

نشاندن گراف در فضاهایی با ابعاد بالاتر

اعتقاد بر این است که هر گراف محدود در یک فضای سه‌بعدی قابل نشاندن است.
یک روش برای انجام این موضوع این است که نقاط را در هر خط درون فضا قرار دهیم و لبه‌ها را همانند منحنی‌های هر یک از آن‌ها در یک نیم سطح مجزا ترسیم کنیم به طوری که هر نیم سطح آن خطوط را به عنوان مرز مشترک خودشان دارا هستند. چنین نشاندنی که در آن لبه‌ها در نیم سطح ترسیم می‌شوند نشاندن کتابی گراف نامیده می‌شود. این استعاره از این تصور سرچشمه می‌گیرد که هر یک از سطح‌ها که در آن یک لبه ترسیم می‌شود همانند برگی از کتاب می‌باشد. در واقعیت مشاهده شد که لبه‌های متعددی ممکن است در یک صفحهٔ مشابه ترسیم شود. ضخامت کتاب گراف حداقل تعداد نیم‌صفحه‌های مورد نیاز برای چنین ترسیمی می‌باشد.
متناوباً هر گراف محدود می‌تواند با لبه‌های مستقیم در سه بعد بدون تقاطع توسط قراردادن راس‌های آن در موقعیت معمولی ترسیم شود؛ بنابراین هر گراف چهار لبه‌ای هم سطح نمی‌باشند. به‌طور مثال این موضوع با قراردادن راس iام در نقطهٔ (I,i2,i3) منحنی لحظه‌ای بدست آید.
نشاندن گراف در فضای سه‌بعدی به طوری که هیچ ۲ چرخه‌ای از نظر مکانی متصل نباشند، نشاندن بدون اتصال نامیده می‌شوند. یک گراف نشاندن بدون اتصال دارد اگر و تنها اگر هیچ‌یک از ۷ گراف خانوادهٔ پترسن را به عنوان گراف فرعی نداشته باشد.