DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2025.16

Listing Spanning Trees of Outerplanar Graphs by Pivot-Exchanges

Authors: Nastaran Behrooznia and Torsten Mütze

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract

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.

Cite as

Nastaran Behrooznia and Torsten Mütze. Listing Spanning Trees of Outerplanar Graphs by Pivot-Exchanges. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{behrooznia_et_al:LIPIcs.STACS.2025.16,
  author =	{Behrooznia, Nastaran and M\"{u}tze, Torsten},
  title =	{{Listing Spanning Trees of Outerplanar Graphs by Pivot-Exchanges}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{16:1--16:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.16},
  URN =		{urn:nbn:de:0030-drops-228411},
  doi =		{10.4230/LIPIcs.STACS.2025.16},
  annote =	{Keywords: Spanning tree, generation, edge exchange, Hamilton path, Gray code}
}

Search Results

Documents authored by Behrooznia, Nastaran

Listing Spanning Trees of Outerplanar Graphs by Pivot-Exchanges

Abstract

Cite as

Thanks for your feedback!

Could not send message