Title of article :
Algorithms and outerplanar conditions for A-trails in plane Eulerian graphs Original Research Article
Author/Authors :
Lars D?vling Andersen، نويسنده , , Herbert Fleischner، نويسنده , , Susanne Regner، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 1998
Abstract :
The problem of finding A-trails in plane Eulerian graphs is NP-complete even for 3-connected graphs, as shown by the first two authors in an earlier paper. In the present paper, we discuss sufficient conditions for the existence of an A-trail in a 2-connected plane Eulerian graph. They generalize the result that simple 2-connected outerplane Eulerian graphs always have A-trails; we give a polynomial algorithm for finding A-trails in such graphs and show that this algorithm also works for certain multigraphs.
Journal title :
Discrete Applied Mathematics
Journal title :
Discrete Applied Mathematics