Induced circuits in planar graphs
type: Item
instance of: scholarly article
title: Induced circuits in planar graphs
zbMATH Open document ID: 0794.05121
author: V. Pereyra
published in: Journal of Combinatorial Theory. Series B
publication date: 1994-05-05T00:00:00Z
full work available at URL: induced-circuits-in-planar-graphs(e971b42e-1bb8-4759-8bd5-cf55ca6b7c29).html
review text: Previously the authors have given a polynomial-time algorithm for the problem of finding a minimum cost circuit without chords (induced circuit) traversing two given vertices of a planar graph. The algorithm is based on the Ellipsoid Method. Here we give an \(O(n^ 2)\) combinatorial algorithm to determine whether two nodes in a planar graph lie on an induced circuit. We also give a min-max relation for the problem of finding a maximum number of paths connecting two given vertices in a planar graph so that each pair of these paths forms an induced circuit.
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 562401
zbMATH Keywords: universal covering surface
zbMATH Keywords: ellipsoid method
zbMATH Keywords: polynomial-time algorithm
zbMATH Keywords: planar graph
zbMATH Keywords: induced circuit
MaRDI profile type: Publication
OpenAlex ID: W2028803564
DOI: 10.1006/JCTB.1994.1011
description: scientific article; zbMATH DE number 562401