Algorithms and outerplanar conditions for \(A\)-trails in plane Eulerian graphs
type: Item
instance of: scholarly article
title: Algorithms and outerplanar conditions for \(A\)-trails in plane Eulerian graphs
zbMATH Open document ID: 0904.05060
DOI: 10.1016/S0166-218X(97)00141-8
author: Lars Døvling Andersen
author: Herbert Fleischner
author: Susanne Regner
published in: Discrete Applied Mathematics
publication date: 1998-07-28T00:00:00Z
full work available at URL: dam
review text: An \(A\)-trail in a plane Eulerian multigraph is an Eulerian trail with the property that consecutive edges of the trail, say \((v_{i-1}, v_i)\) and \((v_i, v_{i+1})\), are always neighbours in the cyclic ordering of the edges incident with \(v_i\) defined by the clockwise order in the plane representation. The problem of finding \(A\)-trails in plane Eulerian graphs is NP-complete even for 3-connected graphs. Some sufficient conditions for the existence of \(A\)-trails are proved. Algorithmic aspects are discussed.
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 1180345
zbMATH Keywords: plane graphs
zbMATH Keywords: outerplanar graphs
zbMATH Keywords: \(A\)-trail
zbMATH Keywords: Eulerian trail
zbMATH Keywords: plane Eulerian graphs
reviewed by: G. Gutin
MaRDI profile type: Publication
cites work: The NP-completeness of finding A-trails in Eulerian graphs and of finding spanning trees in hypergraphs
cites work: Q5545841
cites work: The importance of being Euler
cites work: Eulerian graphs and related topics. Part 1, Volume 1
cites work: Q4121921
cites work: A Theorem on Planar Graphs
cites work: Q3785974
OpenAlex ID: W2049344114
Recommended article: The algorithms for the Eulerian cycle and Eulerian trail problems for a multiple graph
Recommended article: Finding Double Euler Trails of Planar Graphs in Linear Time
Recommended article: The NP-completeness of finding A-trails in Eulerian graphs and of finding spanning trees in hypergraphs
Recommended article: Q4207932
Recommended article: On the number of Euler trails in directed graphs
Recommended article: Trees and Euler Tours in a Planar Graph and its Relatives
Recommended article: On circuit decomposition of planar Eulerian graphs
Recommended article: Q3758847
Recommended article: An algorithm for outerplanar graphs with parameter
description: scientific article; zbMATH DE number 1180345