تشخيص وتر افزايشي بودن براي چند كلاس از گراف هاي هندسي

يك گراف هندسي را وتر افزايشي گويند هرگاه بين هر دو رأس از گراف، مسيري وجود داشته باشد به طوري كه براي هر چهار نقطه a, b, c و d ه به ترتيب روي مسير قرار گرفته اند، فاصله a و d از فاصله b و c كمتر نباشد. در اين مقاله نشان مي دهيم براي دورها و - o--گراف هاي هندسي با n رأس، در زمان o n^2 ي توان وترافزايشي بودن را تشخيص داد. براي گراف هايي كه هر يال آنها روي حداكثر يك دور قرار دارد و هر دور دقيقا يك رأس برشي دارد. مي توان در زمان(O(n^2 + K^2n كه k مجموع تعداد دورها و رئوس درجه يك گراف و n تعداد رئوس گراف است، وترافزايشي بودن را تشخيص داد. همچنين نشان مي دهيم تشخيص وترافزايشي بودن گراف هاي هندسي متعامد با n رأس و m يال در زمان ( O(nm ممكن است.