Computer Sciences Dept.

On Non-Intersecting Eulerian Circuits

Samuel W Bent and Udi Manber

The following question arises in flame-cutting and similar applications. "Given a graph drawn in the plane, is there an Eulerian circuit in which successive edges always belong to a common face?" We prove that this question and related ones are NP-complete

Download this report (PDF)

Return to tech report index

Computer Science | UW Home