Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-09T01:52:44.728Z Has data issue: false hasContentIssue false
  • English
  • Français

Minor-Minimal Planar Graphs of Even Branch-Width

Published online by Cambridge University Press:  03 September 2010

TORSTEN INKMANN  and
ROBIN THOMAS
TORSTEN INKMANN
Affiliation:
School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332-0160, USA (e-mail: torsten.inkmann@gmail.com, thomas@math.gatech.edu)
ROBIN THOMAS
Affiliation:
School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332-0160, USA (e-mail: torsten.inkmann@gmail.com, thomas@math.gatech.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Let k ≥ 1 be an integer, and let H be a graph with no isolated vertices embedded in the projective plane, such that every homotopically non-trivial closed curve intersects H at least k times, and the deletion and contraction of any edge in this embedding results in an embedding that no longer has this property. Let G be the planar double cover of H obtained by lifting G into the universal covering space of the projective plane, the sphere. We prove that G is minor-minimal of branch-width 2k. We also exhibit examples of minor-minimal planar graphs of branch-width 6 that do not arise in this way.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 20 , Issue 1 , January 2011 , pp. 73 - 82
Copyright
Copyright © Cambridge University Press 2010

References

[1]Barnette, D. (1991) The minimal projective plane polyhedral maps. In Applied Geometry and Discrete Mathematics, Vol. 4 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci., AMS, pp. 63–70.Google Scholar
[2]Bodlaender, H. L. and Thilikos, D. M. (1999) Graphs with branchwidth at most three. J. Algorithms 32 167–194.CrossRefGoogle Scholar
[3]Dharmatilake, J. (1994) Binary matroids with branch-width three. PhD thesis, Ohio State University.Google Scholar
[4]Inkmann, T. (2008) Tree-based decompositions of graphs on surfaces and applications to the traveling salesman problem. PhD dissertation, Georgia Institute of Technology.Google Scholar
[5]Johnson, E. and Robertson, N. Private communication.Google Scholar
[6]Lins, S. (1981) A minimax theorem on circuits in projective graphs. J. Combin. Theory Ser. B 30 253–262.CrossRefGoogle Scholar
[7]Mohar, B. and Thomassen, C. (2001) Graphs on Surfaces, Johns Hopkins University Press.CrossRefGoogle Scholar
[8]Randby, S. P. (1997) Minimal embeddings in the projective plane. J. Graph Theory 25 153–164.3.0.CO;2-L>CrossRefGoogle Scholar
[9]Robertson, N. and Seymour, P. D. (1990) Graph minors IV: Tree-width and well-quasi-ordering. J. Combin. Theory Ser. B 48 227–254.CrossRefGoogle Scholar
[10]Schrijver, A. (1991) Decomposition of graphs on surfaces and a homotopic circulation theorem. J. Combin. Theory Ser. B 51 161–210.CrossRefGoogle Scholar
[11]Schrijver, A. (1992) On the uniqueness of kernels. J. Combin. Theory Ser. B 55 146–160.CrossRefGoogle Scholar
[12]Schrijver, A. (1994) Classification of minimal graphs of given representativity on the torus. J. Combin. Theory Ser. B 61 217–236.CrossRefGoogle Scholar
[13]Seymour, P. D. and Thomas, R. (1994) Call routing and the ratcatcher. Combinatorica 14 217–241.CrossRefGoogle Scholar
[14]Vitray, R. P. (1993) Representativity and flexibility on the projective plane. In Graph Structure Theory (Seattle, WA, 1991), Vol. 147 of Contemp. Math., AMS, pp. 341–347.CrossRefGoogle Scholar