A simple and robust algorithm for bisecting a triconnected graph with two resource sets

摘要

In this paper, by proposing a new way of maintaining positions of points in the plane, we designed an O(|V|{sup}2) time and space algorithm for bisecting a given 3-connected graph G = (V, E). Although our algorithm runs faster but needs more space than the previously known algorithm, it requires to store lists of integers with size O(|V|) and is robust against a large size of instance. It is the future research to apply our representation method for positions to other geometric problems.