Branchwidth is ( 1, g )-self-dual
Authors: 
Georgios Kontogeorgiou, Alexandros Leivaditis, Kostas I. Psaromiligkos, Giannos Stamoulis, Dimitris ZorosAuthors Info & Claims
References
[1]
Amini Omid, Huc Florian, Pérennes Stéphane, On the path-width of planar graphs, SIAM J. Discrete Math. 23 (3) (2009) 1311–1316.
[2]
Barrière Lali, Flocchini Paola, Fomin Fedor V., Fraigniaud Pierre, Nisse Nicolas, Santoro Nicola, Thilikos Dimitrios M., Connected graph searching, Inf. Comput. 219 (2012) 1–16.
[3]
Bodlaender Hans L., Fomin Fedor V., Approximation of pathwidth of outerplanar graphs, J. Algorithms 43 (2) (2002) 190–200.
[4]
Bouchitté Vincent, Mazoit Frédéric, Todinca Ioan, Chordal embeddings of planar graphs, Discrete Math. 273 (1) (2003) 85–102.
[5]
Coudert David, Huc Florian, Sereni Jean-Sébastien, Pathwidth of outerplanar graphs, J. Graph Theory 55 (1) (2007) 27–41.
[6]
Fomin Fedor V., Thilikos Dimitrios M., On self duality of pathwidth in polyhedral graph embeddings, J. Graph Theory 55 (1) (2007) 42–54.
[7]
Geelen James F., Gerards Albertus M.H., Whittle Geoff, Branch-width and well-quasi-ordering in matroids and graphs, J. Combin. Theory Ser. B 84 (2) (2002) 270–290.
[8]
Gu Qian-Ping, Tamaki Hisao, Optimal branch-decomposition of planar graphs in O(n3) time, ACM Trans. Algorithms 4 (3) (2008) 30:1–30:13.
[9]
Hicks Illya V., McMurray Nolan B., The branchwidth of graphs and their cycle matroids, J. Combin. Theory Ser. B 97 (5) (2007) 681–692.
[10]
Kashyap Navin, Matroid pathwidth and code trellis complexity, SIAM J. Discrete Math. 22 (1) (2008) 256–272.
[11]
Koutsonas Athanassios, Thilikos Dimitrios M., Yamazaki Koichi, Outerplanar obstructions for matroid pathwidth, Discrete Math. 315–316 (2014) 95–101.
[12]
Lapoire Denis, Treewidth and duality for planar hypergraphs, 1996, Manuscript.
[13]
Mäkinen Erkki, How to draw a hypergraph, Int. J. Comput. Math. 34 (3–4) (1990) 177–185.
[14]
Mazoit Frédéric, Décomposition Algorithmique des Graphes, (Ph.D. thesis) École Normale Supérieure de Lyon, 2004.
[15]
Mazoit Frédéric, Tree-width of graphs and surface duality, J. Combin. Theory Ser. B 102 (3) (2012) 671–687.
[16]
Mazoit Frédéric, Thomassé Stéphan, Branchwidth of graphic matroids, in: Surveys in Combinatorics 2007, in: London Mathematical Society Lecture Note Series, Vol. 346, Cambridge University Press, 2007, pp. 275–286.
[17]
Mohar Bojan, Thomassen Carsten, Graphs on Surfaces, John Hopkins University Press, 2001.
[18]
Oxley James, Matroid Theory, in: Oxford Graduate Texts in Mathematics, Vol. 21, second ed., Oxford University Press, Oxford, 2011, p. xiv+684.
[19]
Robertson Neil, Seymour Paul D., Graph minors. III. Planar tree-width, J. Combin. Theory Ser. B 36 (1984) 49–64.
[20]
Robertson Neil, Seymour Paul D., Graph minors. X. Obstructions to tree-decomposition, J. Combin. Theory Ser. B 52 (2) (1991) 153–190.
[21]
Robertson Neil, Seymour Paul D., Graph minors. XX. Wagner’s conjecture, J. Combin. Theory Ser. B 92 (2) (2004) 325–357. Special Issue Dedicated to Professor W.T. Tutte.
[22]
Sau Ignasi, Thilikos Dimitrios M., On self-duality of branchwidth in graphs of bounded genus, Discrete Appl. Math. 159 (17) (2011) 2184–2186.
[23]
Seymour Paul D., Thomas Robin, Call routing and the ratcatcher, Combinatorica 14 (2) (1994) 217–241.
[24]
Vatshelle Martin, New Width Parameters of Graphs, (Ph.D. thesis) University of Bergen, 2012.
Recommendations
Edge-maximal graphs of branchwidth k: The k-branches
Treewidth and branchwidth are two closely related connectivity parameters of graphs. Graphs of treewidth at most k have well-known alternative characterizations as subgraphs of chordal graphs and as partial k-trees. In this paper we give analogous ...
On self-duality of branchwidth in graphs of bounded genus
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, ...
Graphs with Branchwidth at Most Three
In this paper we investigate both the structure of graphs with branchwidth at most three, as well as algorithms to recognise such graphs. We show that a graph has branchwidth at most three if and only if it has treewidth at most three and does not ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Elsevier B.V.
Publisher
Elsevier Science Publishers B. V.
Netherlands
Publication History
Published: 09 July 2024
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 25 Nov 2024
Other Metrics
Citations
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in