On non-intersecting Eulerian circuits
type: Item
instance of: scholarly article
title: On non-intersecting Eulerian circuits
zbMATH Open document ID: 0621.05022
DOI: 10.1016/0166-218X(87)90045-X
author: Samuel W. Bent
author: Udi Manber
published in: Discrete Applied Mathematics
publication date: 1987-01-01T00:00:00Z
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.
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4006297
zbMATH Keywords: flame-cutting
zbMATH Keywords: Eulerian circuit
MaRDI profile type: Publication
cites work: Q4198056
cites work: Q5585020
cites work: Planar Formulae and Their Uses
Recommended article: On circuit decomposition of planar Eulerian graphs
Recommended article: Covering and Euler cycles on non-oriented graphs
Recommended article: On even circuit decompositions of eulerian graphs
Recommended article: Circuit decompositions of Eulerian graphs
Recommended article: Q3717077
Recommended article: Q4013126
Recommended article: Eulerian Circuits with No Monochromatic Transitions in Edge-colored Digraphs
Recommended article: Q4207932
Recommended article: On circuits in graphs
description: scientific article; zbMATH DE number 4006297