On self-duality of branchwidth in graphs of bounded genus

Ignasi Sau, Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review


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*)≤6·bw(G)+2g-4 for any graph G embedded in a surface of Euler genus g.

Original languageEnglish (US)
Pages (from-to)2184-2186
Number of pages3
JournalDiscrete Applied Mathematics
Issue number17
StatePublished - Oct 28 2011


  • Branchwidth
  • Duality
  • Graphs on surfaces
  • Polyhedral embedding

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'On self-duality of branchwidth in graphs of bounded genus'. Together they form a unique fingerprint.

Cite this