Edge-disjoint homotopic paths in a planar graph with one hole

Planar graphs; geometric and topological aspects of graph theory (05C10) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Graph theory (including graph drawing) in computer science (68R10)

Review text

We prove the following theorem, conjectured by K. Mehlhorn: Let \(G=(V,E)\) be a planar graph, embedded in \({\mathbb{R}}^ 2\). Let 0 denote the interior of the unbounded face. Let I be the interior of some fixed bounded face. Let \(C_ 1,...,C_ k\) be curves in \({\mathbb{R}}^ 2\setminus (I\cup 0)\), with end points in \(V\cap \delta (I\cup 0)\), so that for each vertex v of G the degree of v in G has the same parity (mod 2) as the number of curves \(C_ i\) beginning or ending in v (counting a curve beginning and ending in v for two). Then there exist pairwise edge-disjoint paths \(P_ 1,...,P_ k\) in G so that \(P_ i\) is homotopic to \(C_ i\) in the space \({\mathbb{R}}^ 2\setminus (I\cup 0)\) for \(i=1,...,k\), if and only if for each dual path Q from \(I\cup 0\) to \(I\cup 0\) the number of edges in Q is not smaller than the number of times Q necessarily intersects the curves \(C_ i.\) The theorem generalizes a theorem of Okamura and Seymour. Its proof yields a polynomial-time algorithm finding the paths as required.

Recommendations

Cites work

Cited in

(12)

This page was built for publication: Edge-disjoint homotopic paths in a planar graph with one hole

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1097900)