XII Preface solution as efficiently as possible. Most of the problems we treat have a good
algorithmic solution, but we also show how even difficult problems can be treated (for …

We give a linear-time algorithm for single-source shortest paths in planar graphs with
nonnegative edge-lengths. Our algorithm also yields a linear-time algorithm for maximum …

Collected in this volume are most of the important theorems and algorithms currently known
for planar graphs, together with constructive proofs for the theorems. Many of the algorithms …

Network flow problems are central problems in operations research, computer science, and
engineering and they arise in many real world applications. Starting with early work in linear …

We give an O(n\log^3n) algorithm that, given an n-node directed planar graph with arc
capacities, a set of source nodes, and a set of sink nodes finds a maximum flow from the …

We give the first correct O (n log n) algorithm for finding a maximum st-flow in a directed
planar graph. After a preprocessing step that consists in finding single-source shortest-path …

We give a linear-time algorithm for single-source shortest paths in planar graphs with
nonnegative edgelengths. Our algorithm also yields a linear-time algorithm for maximum …

The problem of maximum flow in planar graphs has always been investigated under the
assumption that there is only one source and one sink. Here we consider the case where …

Given a triangulated planar graph G on n vertices and an integer r< n, an r--division of G with
few holes is a decomposition of G into O (n/r) regions of size at most r such that each region …

This paper considers weight-maximizing variants of the classical symmetric and asymmetric
traveling-salesman problems. Like their weight-minimizing counterparts, these variants are …