Abstract
A graph G is a 2-tree if G = K3 or G has a vertex v of degree 2, whose neighbours are adjacent, and G\v is a 2-tree. A characterization of the degree sequences of 2-trees is given. This characterization yields a linear-time algorithm for recognizing and realizing degree sequences of 2-trees.
Original language | English |
---|---|
Title of host publication | Proceedings of the 9th Workshop on Algorithm Engineering and Experiments and the 4th Workshop on Analytic Algorithms and Combinatorics |
Pages | 232-241 |
Number of pages | 10 |
Publication status | Published - 22 Aug 2007 |
Externally published | Yes |
Event | 9th Workshop on Algorithm Engineering and Experiments and the 4th Workshop on Analytic Algorithms and Combinatorics - New Orleans, LA, United States of America Duration: 6 Jan 2007 → 6 Jan 2007 |
Conference
Conference | 9th Workshop on Algorithm Engineering and Experiments and the 4th Workshop on Analytic Algorithms and Combinatorics |
---|---|
Country/Territory | United States of America |
City | New Orleans, LA |
Period | 6/01/07 → 6/01/07 |
Keywords
- 2-tree
- Degree sequence
- Graphical degree sequence
- K-tree
- Series-parallel graph
- Treewidth