Search results for "String graph"

Searching for a strong double tracing in a graph

1998

Given a connected graph G, we present a polynomial algorithm which either finds a tour traversing each edge of G exactly two non-consecutive times, one in each direction, or decides that no such tour exists. The main idea of this algorithm is based on the modification of a proof given by Thomassen related to a problem proposed by Ore in 1951.