Vol. 7, No. 2, 2014

 Recent Issues
 The Journal About the Journal Subscriptions Editorial Board Editors’ Interests Scientific Advantages Submission Guidelines Submission Form Ethics Statement Editorial Login Author Index Coming Soon Contacts ISSN: 1944-4184 (e-only) ISSN: 1944-4176 (print) Other MSP Journals
Spanning tree congestion of planar graphs

Hiu Fai Law, Siu Lam Leung and Mikhail I. Ostrovskii

Vol. 7 (2014), No. 2, 205–226
Abstract

This paper is devoted to estimates of the spanning tree congestion for some planar graphs. We present three main results: (1) We almost determined (up to $±1$) the maximal possible spanning tree congestion for planar graphs. (2) The value of congestion indicator introduced by Ostrovskii [Discrete Math. 310, 1204–1209] can be very far from the value of the spanning tree congestion. (3) We find some more examples in which the congestion indicator can be used to find the exact value of the spanning tree congestion.

Keywords
dual graph, dual spanning tree, minimum congestion spanning tree, planar graph
Mathematical Subject Classification 2010
Primary: 05C05
Secondary: 05C10, 05C35