Algorithms and outerplanar conditions for \(A\)-trails in plane Eulerian graphs

DOI10.1016/S0166-218X(97)00141-8zbMath0904.05060OpenAlexW2049344114MaRDI QIDQ1392551

Lars Døvling Andersen, Susanne Regner, Herbert Fleischner

Publication date: 28 July 1998

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

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

outerplanar graphsplane graphsEulerian trail\(A\)-trailplane Eulerian graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45)

Related Items (5)

On Finding Hamiltonian Cycles in Barnette Graphs ⋮ The NP-completeness of finding A-trails in Eulerian graphs and of finding spanning trees in hypergraphs ⋮ A-trails of embedded graphs and twisted duals ⋮ DNA origami and unknotted A-trails in torus graphs ⋮ DNA origami and the complexity of Eulerian circuits with turning costs

Cites Work

• Eulerian graphs and related topics. Part 1, Volume 1
• The importance of being Euler
• The NP-completeness of finding A-trails in Eulerian graphs and of finding spanning trees in hypergraphs
• A Theorem on Planar Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Algorithms and outerplanar conditions for \(A\)-trails in plane Eulerian graphs