On Non-Intersecting Eulerian Circuits
Loading...
Files
Date
Authors
Bent, Samuel W
Manber, Udi
Advisors
License
DOI
Type
Technical Report
Journal Title
Journal ISSN
Volume Title
Publisher
University of Wisconsin-Madison Department of Computer Sciences
Grantor
Abstract
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
Description
Keywords
Related Material and Data
Citation
TR546