Induced circuits in planar graphs (Q1322013): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 03:56, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Induced circuits in planar graphs |
scientific article |
Statements
Induced circuits in planar graphs (English)
0 references
5 May 1994
0 references
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.
0 references
universal covering surface
0 references
ellipsoid method
0 references
polynomial-time algorithm
0 references
planar graph
0 references
induced circuit
0 references