On self-duality of branchwidth in graphs of bounded genus

Ignasi Sau; Dimitrios M. Thilikos

doi:10.1016/j.dam.2011.06.028

On self-duality of branchwidth in graphs of bounded genus

Ignasi Sau, Dimitrios M. Thilikos

Computer Science

Research output: Contribution to journal › Article › peer-review

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 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 language	English (US)
Pages (from-to)	2184-2186
Number of pages	3
Journal	Discrete Applied Mathematics
Volume	159
Issue number	17
DOIs	https://doi.org/10.1016/j.dam.2011.06.028
State	Published - Oct 28 2011

Keywords

Branchwidth
Duality
Graphs on surfaces
Polyhedral embedding

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/j.dam.2011.06.028

Cite this

@article{dc42090320eb4f7e9471079dbbb17b73,

title = "On self-duality of branchwidth in graphs of bounded genus",

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 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.",

keywords = "Branchwidth, Duality, Graphs on surfaces, Polyhedral embedding",

author = "Ignasi Sau and Thilikos, {Dimitrios M.}",

year = "2011",

month = oct,

day = "28",

doi = "10.1016/j.dam.2011.06.028",

language = "English (US)",

volume = "159",

pages = "2184--2186",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier",

number = "17",

}

TY - JOUR

T1 - On self-duality of branchwidth in graphs of bounded genus

AU - Sau, Ignasi

AU - Thilikos, Dimitrios M.

PY - 2011/10/28

Y1 - 2011/10/28

N2 - 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.

AB - 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.

KW - Branchwidth

KW - Duality

KW - Graphs on surfaces

KW - Polyhedral embedding

UR - http://www.scopus.com/inward/record.url?scp=80052583871&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=80052583871&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2011.06.028

DO - 10.1016/j.dam.2011.06.028

M3 - Article

AN - SCOPUS:80052583871

SN - 0166-218X

VL - 159

SP - 2184

EP - 2186

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 17

ER -

On self-duality of branchwidth in graphs of bounded genus

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this