## Abstract / Description of output

We give a simple polynomial-time algorithm to exactly count the number of Euler tours (ETs) of any Eulerian generalized series-parallel graph, and show how to adapt this algorithm to exactly sample a random ET of the given generalized series-parallel graph. Note that the class of generalized series-parallel graphs includes all outerplanar graphs. We can perform the counting in time *O*(*m*Δ^{3}), where Δ is the maximum degree of the graph with *m* edges. We use *O*(*mn*Δ^{2}logΔ) bits to store intermediate values during our computations. To date, these are the first known polynomial-time algorithms to count or sample ETs of any class of graphs; there are no other known polynomial-time algorithms to even approximately count or sample ETs of any other class of graphs. The problem of counting ETs is known to be *#P*-complete for general graphs (Brightwell and Winkler, 2005 [2]) also for planar graphs (Creed, 2010 [3]).

Original language | English |
---|---|

Pages (from-to) | 110-122 |

Number of pages | 13 |

Journal | Journal of Discrete Algorithms |

Volume | 10 |

Issue number | n/a |

DOIs | |

Publication status | Published - Jan 2012 |

## Keywords / Materials (for Non-textual outputs)

- Euler tour
- Series-parallel graph