2026-07-21T20:43:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22841 2025-10-02T13:35:11Z ddc:004 open_access

Listing Spanning Trees of Outerplanar Graphs by Pivot-Exchanges Behrooznia, Nastaran Mütze, Torsten Spanning tree generation edge exchange Hamilton path Gray code We prove that the spanning trees of any outerplanar triangulation G can be listed so that any two consecutive spanning trees differ in an exchange of two edges that share an end vertex. For outerplanar graphs G with faces of arbitrary lengths (not necessarily 3) we establish a similar result, with the condition that the two exchanged edges share an end vertex or lie on a common face. These listings of spanning trees are obtained from a simple greedy algorithm that can be implemented efficiently, i.e., in time {O}(n log n) per generated spanning tree, where n is the number of vertices of G. Furthermore, the listings correspond to Hamilton paths on the 0/1-polytope that is obtained as the convex hull of the characteristic vectors of all spanning trees of G. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nastaran Behrooznia and Torsten Mütze 2025 Is Part Of LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2025.16 urn:nbn:de:0030-drops-228411 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.16 eng https://creativecommons.org/licenses/by/4.0/legalcode