  The Stackelberg Minimum Spanning Tree Game is a two-level combinatorial
pricing problem played on a graph representing a network. Its edges are colored
either red or blue, and the red edges have a given fixed cost, representing the
competitor's prices. The first player chooses an assignment of prices to the
blue edges, and the second player then buys the cheapest spanning tree, using
any combination of red and blue edges. The goal of the first player is to
maximize the total price of purchased blue edges.
  We study this problem in the cases of planar and bounded-treewidth graphs. We
show that the problem is NP-hard on planar graphs but can be solved in
polynomial time on graphs of bounded treewidth.
