Spanning tree congestion of k-outerplanar graphs

摘要

We investigate the spanning tree congestion of k-outerplanar graphs. In 1987, Simonson [Math. Syst. Theory 20 (1987) 235-252] conjectured that every k-outerplanar graph has spanning tree congestion at most k times its maximum degree. We settle this conjecture affirmatively. We also show that the spanning tree congestion of outerplanar graphs can be determined in linear time.