My UW | UW Search

   
   

Computer Science Home Page
 
 
 
Computer Sciences Dept.

On Non-Intersecting Eulerian Circuits

Samuel W Bent and Udi Manber
1984

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

Feedback or content questions: send email to "pubs" at the cs.wisc.edu server
Technical or accessibility issues: lab@cs.wisc.edu
Copyright © 2002, 2003, 2004, 2005, 2006, 2007  The Board of Regents of the University of Wisconsin System.