Characterizing 3-Connected Planar Graphs and Graphic Matroids

Autor(es)

Lemos, Manoel ^[1] ; Reid, Talmage James ^[2] ; Wu, Haidong ^[2]

Afiliação do(s) autor(es)

^[1] Univ Fed Pernambuco, Dept Matemat, Recife, PE - Brazil

^[2] Univ Mississippi, Dept Math, University, MS 38677 - USA

• Tipo de documento: Artigo Científico
• Fonte: JOURNAL OF GRAPH THEORY; v. 64, n. 2, p. 165-174, JUN 2010.
• Citações Web of Science: 3

Resumo

A well-known result of Tutte states that a 3-connected graph G is planar if and only if every edge of G is contained in exactly two induced non-separating circuits. Bixby and Cunningham generalized Tutte's result to binary matroids. We generalize both of these results and give new characterizations of both 3-connected planar graphs and 3-connected graphic matroids. Our main result determines when a natural necessary condition for a binary matroid to be graphic is also sufficient. (C) 2009 Wiley Periodicals, Inc. J Graph Theory 64: 165-174, 2010 (AU)

• Processo FAPESP: 03/09925-5 - Fundamentos da ciência da computação: algoritmos combinatórios e estruturas discretas
• Beneficiário: Yoshiharu Kohayakawa
• Modalidade de apoio: Auxílio à Pesquisa - Programa PRONEX - Temático