Vol. 7, No. 2, 2014

Download this article
Download this article For screen
For printing
Recent Issues

Volume 17
Issue 4, 543–722
Issue 3, 363–541
Issue 2, 183–362
Issue 1, 1–182

Volume 16, 5 issues

Volume 15, 5 issues

Volume 14, 5 issues

Volume 13, 5 issues

Volume 12, 8 issues

Volume 11, 5 issues

Volume 10, 5 issues

Volume 9, 5 issues

Volume 8, 5 issues

Volume 7, 6 issues

Volume 6, 4 issues

Volume 5, 4 issues

Volume 4, 4 issues

Volume 3, 4 issues

Volume 2, 5 issues

Volume 1, 2 issues

The Journal
About the journal
Ethics and policies
Peer-review process
 
Submission guidelines
Submission form
Editorial board
Editors' interests
 
Subscriptions
 
ISSN 1944-4184 (online)
ISSN 1944-4176 (print)
 
Author index
To appear
 
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
Milestones
Received: 19 March 2013
Revised: 2 July 2013
Accepted: 3 July 2013
Published: 16 November 2013

Communicated by Joseph A. Gallian
Authors
Hiu Fai Law
Department of Mathematics
Universität Hamburg
55 Bunderstrasse
D-20146 Hamburg
Germany
Siu Lam Leung
Department of Mathematics and Computer Science
St. John’s University
8000 Utopia Parkway
Queens, NY 11439
United States
Mikhail I. Ostrovskii
Department of Mathematics and Computer Science
St. John’s University
8000 Utopia Parkway
Queens, NY 11439
United States