Department of
Applied
Mathematics

Extending partial plane embeddings

Vít Jelínek

Abstract

(joint work with Jan Kratochvil, Maurizio Patrignani, and Ignaz Rutter)

The topic of my talk is the following decision problem, called PREEMBEDDED PLANARITY:

Input: a graph H with a prescribed plane embedding, and a graph G that contains H as a subgraph. Question: is it possible to extend the prescribed embedding of H into a plane embedding of the whole graph G?

I will present a polynomial-time algorithm that solves this decision problem. The main tool of the algorithm is the data structure known as SPQR tree, which allows to concisely represent all possible embeddings of a given planar graph. I will also mention several optimization problems related to PREEMBEDDED PLANARITY, which turn out to be NP-complete.