Tree polytope on 2-trees (Q1322553): Difference between revisions

The class of 2-tree graphs is defined inductively as follows: start with a single edge and add nodes by joining them to the two endpoints of an existing edge. Many NP-complete problems on graphs are polynomial when restricted to this class of graphs. In particular, the Steiner Tree problem is linear time solvable on graphs in this class. It is this observation that motivates the authors main result: a linear characterization of the convex hull of the characteristic vectors of trees of 2-free graphs.