Abstract
A graph parameter is self-dual in some class of graphs embeddable in some surface if its value does not change in the dual graph more than a constant factor. Self-duality has been examined for several width-parameters, such as branchwidth, pathwidth, and treewidth. In this paper, we give a direct proof of the self-duality of branchwidth in graphs embedded in some surface. In this direction, we prove that bw(G∗) < 6 • bw(G) + 2g - 4 for any graph G embedded in a surface of Euler genus g.
| Original language | English (US) |
|---|---|
| Pages | 19-22 |
| Number of pages | 4 |
| State | Published - 2009 |
| Event | 8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2009 - Paris, France Duration: Jun 2 2009 → Jun 4 2009 |
Conference
| Conference | 8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2009 |
|---|---|
| Country/Territory | France |
| City | Paris |
| Period | 6/2/09 → 6/4/09 |
Keywords
- Branchwidth
- Duality
- Graphs on surfaces
- Polyhedral embedding
ASJC Scopus subject areas
- Control and Optimization
- Discrete Mathematics and Combinatorics