### Abstract

Fleischner's theorem says that the square of every 2-connected graph contains a Hamiltonian cycle. We present a proof resulting in an O(|E|) algorithm for producing a Hamiltonian cycle in the square G

^{2}of a 2-connected graph G = (V, E). The previous best was O(|V|^{2}) by Lau in 1980. More generally, we get an O(|E|) algorithm for producing a Hamiltonian path between any two prescribed vertices, and we get an O(|V|^{2}) algorithm for producing cycles C_{3}, C_{4}, …, C|V| in G^{2}of lengths 3,4, …, |V|, respectively.Original language | English |
---|---|

Title of host publication | Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms |

Publisher | Society for Industrial and Applied Mathematics |

Publication date | 2018 |

Pages | 1645-1649 |

ISBN (Electronic) | 978-1-61197-503-1 |

DOIs | |

Publication status | Published - 2018 |

Event | 29th Annual ACM-SIAM Symposium on Discrete Algorithms - Astor Crowne Plaze, New Orleans French Quarter , New Orleans , United States Duration: 7 Jan 2018 → 10 Jan 2018 Conference number: 29 |

### Conference

Conference | 29th Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Number | 29 |

Location | Astor Crowne Plaze, New Orleans French Quarter |

Country | United States |

City | New Orleans |

Period | 07/01/2018 → 10/01/2018 |

Series | Proceedings of the Twenty-ninth Annual Acm-siam Symposium |
---|

## Cite this

Alstrup, S., Georgakopoulos, A., Rotenberg, E., & Thomassen, C. (2018). A hamiltonian cycle in the square of a 2-connected graph in linear time. In

*Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms*(pp. 1645-1649). Society for Industrial and Applied Mathematics. Proceedings of the Twenty-ninth Annual Acm-siam Symposium https://doi.org/10.1137/1.9781611975031.107