انجمن کامپیوتر ایران

گراف دید یک چندضلعی ساده در صفحه گرافی است که مجموعه‌ی رئوس آن، مجموعه رئوس چندضلعی است و هر یال آن معادل با دو راس قابل دید در چندضلعی است. یکی از مسائل قدیمی و مهم هندسه محاسباتی شناسايي ويژگي‌هاي چندضلعی ساده در حالت كلي از روی گراف دید آن است. در همين راستا مروری بر مهم‌ترین پژوهش‌های انجام شده در این شرایط خواهیم داشت. در ادامه شرايط ضروري براي آن كه يك گراف، گراف ديد يك چندضلعي ساده باشد مطرح مي‌كنيم و در پایان نشان مي‌دهيم كه اين شرايط كافي نيستند.