✦ LIBER ✦

Two-Connected Augmentation Problems in Planar Graphs

✍ Scribed by J.Scott Provan; Roger C Burk

Publisher: Elsevier Science
Year: 1999
Tongue: English
Weight: 167 KB
Volume: 32
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.1999.1005

No coin nor oath required. For personal study only.

✦ Synopsis

Given a weighted undirected graph G and a subgraph S of G, we consider the problem of adding a minimum-weight set of edges of G to S so that the resulting Ž . subgraph satisfies specified edge or vertex connectivity requirements between pairs of nodes of S. This has important applications in upgrading telecommunication networks to be invulnerable to link or node failures. We give a polynomial algorithm for this problem when S is connected, nodes are required to be at most 2-connected, and G is planar. Applications to network design and multicommodity cut problems are also discussed.

📜 SIMILAR VOLUMES

Extremal graphs in connectivity augmenta

Extremal graphs in connectivity augmentation

✍ Jord�n, Tibor 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 245 KB 👁 1 views

Let A(n, k, t) denote the smallest integer e for which every kconnected graph on n vertices can be made (k + t)-connected by adding e new edges. We determine A(n, k, t) for all values of n, k, and t in the case of (directed and undirected) edge-connectivity and also for directed vertex-connectivity

Connected subgraphs with small degree su

Connected subgraphs with small degree sums in 3-connected planar graphs

✍ Enomoto, Hikoe; Ota, Katsuhiro 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 213 KB 👁 2 views

It is well-known that every planar graph has a vertex of degree at most five. Kotzig proved that every 3-connected planar graph has an edge xy such that deg(x) + deg(y) ≤ 13. In this article, considering a similar problem for the case of three or more vertices that induce a connected subgraph, we sh

Toughness and longest cycles in 2-connec

Toughness and longest cycles in 2-connected planar graphs

✍ B�hme, T.; Broersma, H. J.; Veldman, H. J. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 390 KB 👁 2 views

Let G be a planar graph on n vertices, let c(G) denote the length of a longest cycle of G, and let w(G) denote the number of components of G. By a well-known theorem of Tutte, c(G) = n (i.e., G is hamiltonian) if G is 4-connected. Recently, Jackson and Wormald showed that c(G) 2 ona for some positiv

Minors in large almost-5-connected non-p

Minors in large almost-5-connected non-planar graphs

✍ Ken-Ichi Kawarabayashi; John Maharry 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 196 KB

## Abstract It is shown that every sufficiently large almost‐5‐connected non‐planar graph contains a minor isomorphic to an arbitrarily large graph from one of six families of graphs. The graphs in these families are also almost‐5‐connected, by which we mean that they are 4‐connected and all 4‐sepa

Two trees in maximal planar bipartite gr

Two trees in maximal planar bipartite graphs

✍ Gerhard Ringel 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB

Solving minimum K-cardinality cut proble

Solving minimum K-cardinality cut problems in planar graphs

✍ Maurizio Bruglieri; Francesco Maffioli; Marco Trubian 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 291 KB