Logo image
Sign in
On self-duality of branchwidth in graphs of bounded genus
Journal article   Open access   Peer reviewed

On self-duality of branchwidth in graphs of bounded genus

Ignasi Sau and Dimitrios M. Thilikos
Discrete Applied Mathematics, Vol.159(17), pp.2184-2186
01/10/2011

Abstract

Branchwidth Duality Graphs on surfaces Polyhedral embedding
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 by 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*) < 6bw(G)+2g-3 for any graph G embedded in a surface of Euler genus g.
url
Find in HALView
url
https://doi.org/10.1016/j.dam.2011.06.028View
Published (Version of record) Open

Metrics

1 Record Views

Details

Logo image