Colloquium Details
Testing Planarity of Partially Embedded Graphs
| Author: | Jan Kratochvil Charles University, Prague |
|---|---|
| Date: | January 15, 2010 |
| Time: | 11:00 |
| Location: | 220 Deschutes |
| Host: | Andrzej Proskurowski |
Abstract
We pose and study the following question: Given a (planar graph) G and a planar embedding of its subgraph H, can this be extended to a noncrossing embedding of the entire graph G? This approach follows the paradigm of completing a partial solution of a particular problem, which has been studied in many different situations before. Unlike in many cases, when the presence of a partial solution in the input makes an otherwise easy problem hard, we show that the planarity question remains polynomial-time solvable. Our algorithm is based on several combinatorial lemmas which show that planarity of partially embedded graphs performs the "oncas" behaviour - obvious necessary conditions for planarity are also sufficient. In particular, a 2-connected graph allows an extension of an embedding of its subgraph H if and only the skeleton of each node of its SPQR-tree has an embedding compatible with the given embedding of H. This implies that no dynamic programming is needed or a decision algorithm, the nodes of the SPQR-tree can be processed independently in parallel. It should be noted that though 2-connected graphs form the core situation, nontrivial steps are needed to handle the less connected cases. By refining the techniques and using appropriately adjusted data structures we manage to achieve a linear time algorithm.
On the other hand we consider several generalizations of the problem, e.g. minimizing the number of edges of the partial embedding that need to be rerouted, and argue that they already become NP-hard.
The talk is based on a joint paper with Patrizio Angelini, Giuseppe Di Battista, Fabrizio Frati, Vit Jelinek, Maurizio Patrignani, and Ignaz Rutter that will be presented at SODA 2010.
Biography
Jan Kratochvil is a full professor and head of the Department of Applied Mathematics at Charles University in Prague, Czech Republic. His major area of work is theoretical computer science, in particular algorithms and complexity in graph theory. He received his Ph.D. at Charles University in 1987 for a thesis about domination and codes in graphs.