Hostname: page-component-cd9895bd7-7cvxr Total loading time: 0 Render date: 2024-12-25T19:04:47.445Z 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: [email protected], [email protected])
ROBIN THOMAS
Affiliation:
School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332-0160, USA (e-mail: [email protected], [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

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

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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