On spanning subgraphs of 4-connected planar graphs
type: Item
instance of: scholarly article
title: On spanning subgraphs of 4-connected planar graphs
zbMATH Open document ID: 0687.05019
DOI: 10.1016/0166-218X(89)90006-1
author: Moshe Rosenfeld
published in: Discrete Applied Mathematics
publication date: 1989-01-01T00:00:00Z
review text: A figure-eight based at v is a pair of cycles having only the single vertex v in common. The author proves that every 4-connected planar graph has a spanning figure-eight subgraph based at v for any \(v\in V(G)\). He provides examples showing that the hypothesis 4-connected is necessary, as is the planarity hypothesis. The author is motivated both by the well- known theorem of Tutte that every 4-connected planar graph is Hamiltonian and by a question on Hamiltonian decompositions. He also shows that finding this figure-eight subgraph is computationally equivalent to finding the Hamiltonian cycle given by Tutte's theorem. It follows that there is an \(O(n^ 3)\)-time algorithm for this problem.
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C45
zbMATH DE Number: 4125422
zbMATH Keywords: figure-eight
zbMATH Keywords: spanning figure-eight subgraph
zbMATH Keywords: planar graph
zbMATH Keywords: Hamiltonian
reviewed by: Dan S. Archdeacon
MaRDI profile type: Publication
cites work: Edge-disjoint Hamilton cycles in 4-regular planar graphs
cites work: Q5422499
cites work: Q4200082
cites work: Q5547252
cites work: Pairs of edge-disjoint Hamiltonian circuits
cites work: From the theory of regular graphs of third and fourth degree
cites work: Matching theory
cites work: Cycles Hamiltoniens dans les graphes 4-réguliers 4-connexes
cites work: Q3680862
cites work: Polytopes of constant weight
cites work: A Theorem on Planar Graphs
description: scientific article; zbMATH DE number 4125422