Characterizing 2-Trees Relative to Chordal and Series-Parallel Graphs

Abstract

The 2-connected 2-tree graphs are defined as being constructible from a single 3-cycle by recursively appending new degree-2 vertices so as to form 3-cycles that have unique edges in common with the existing graph. Such 2-trees can be characterized both as the edge-minimal chordal graphs and also as the edge-maximal series-parallel graphs. These are also precisely the 2-connected graphs that are simultaneously chordal and series-parallel, where these latter two better-known types of graphs have themselves been both characterized and applied in numerous ways that are unmotivated by their interaction with 2-trees and with each other. Toward providing such motivation, the present paper examines several simple, very closely-related characterizations of chordal graphs and 2-trees and, after that, of series-parallel graphs and 2-trees. This leads to showing a way in which chordal graphs and series-parallel graphs are special---indeed, extremal---in this regard.

Keywords

• 2-tree
• chordal graph
• series-parallel graph