## Dominating sets in planar graphs: branch-width and exponential speed-up |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Common terms and phrases

2-connected adjacent Alber apply Lemma Becanse G bijection branch decomposition branch-width bw(G COMPUTATION construct contradiction to property cycle D-dominated E-plane graph D-triangle DAG HAUGLAND decomposition of width define dominating set Dominating Skt problem drawing of G dual graphs dynamic programming E(red(G edge contraction edge set endpoints ext(G G and red(G G is prime graph G Graph Minors holds for G hyperedge hypergraphs implies induced subgraph joined drawing LAMO AND MICHAL Let G main combinatorial result matroids MICHAL WALICKI multiple edges nicely D-dominated E-plane nicely dominated graph Notice pair Planar Dominating Skt planar graph Pmof POLAR DECOMPOSITION PRECONDITIONER prime D-dominated E-plane prime graph proof of Lemma property g region of G resulting graph Robertson & Seymour satisfies property Seymour & Thomas square region subgraph of G Theorem Thomas algorithm tree-width ui(f University of Bergen V(Gi VENANSIUS BARYAMUREEBA vertex set vertices of G YNGVE LAMO