On non-intersecting Eulerian circuits

DOI10.1016/0166-218X(87)90045-XMaRDI QIDQ1090338zbMATH OpenFDO

Authors Samuel W. Bent, Udi Manber

Publication date 1987

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218X(87)90045-X

zbMATH Keywords

Eulerian circuitflame-cutting

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Analysis of algorithms and problem complexity (68Q25)

Review text

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.

Recommendations

• On circuit decomposition of planar Eulerian graphs
• Covering and Euler cycles on non-oriented graphs
• On even circuit decompositions of eulerian graphs
• Circuit decompositions of Eulerian graphs
• scientific article; zbMATH DE number 3946164
• scientific article; zbMATH DE number 63789
• Eulerian Circuits with No Monochromatic Transitions in Edge-colored Digraphs
• scientific article; zbMATH DE number 4128845
• On circuits in graphs

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• Planar Formulae and Their Uses

Cited in

(16)

• Drawing the planar dual
• Finding Hamiltonian circuits in arrangements of Jordan curves is NP- complete
• Dominating sets whose closed stars form spanning trees
• The NP-completeness of finding A-trails in Eulerian graphs and of finding spanning trees in hypergraphs
• Complexity of circuit intersection in graphs
• DNA origami and the complexity of Eulerian circuits with turning costs
• Software for the problem of constructing cutting tool paths in CAD/CAM systems for technological preparation of cutting processes
• Computing Simple Circuits from a Set of Line Segments is NP-Complete
• scientific article; zbMATH DE number 4128845 (Why is no real title available?)
• The topology of scaffold routings on non-spherical mesh wireframes
• Bounding the number of Eulerian tours in undirected graphs
• Refined bounds on the number of Eulerian tours in undirected graphs
• NP-completeness of the Eulerian walk problem for a multiple graph
• Removing popular faces in curve arrangements
• Removing popular faces in curve arrangements
• Some polynomial subclasses of the Eulerian walk problem for a multiple graph

This page was built for publication: On non-intersecting Eulerian circuits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1090338)