[Zurück]

T. Mchedlidze, M. Nöllenburg, I. Rutter:
"Extending Convex Partial Drawings of Graphs";
Algorithmica, 76 (2016), S. 47 - 67.

Given a plane graph G (i.e., a planar graph with a fixed planar embedding
and outer face) and a biconnected subgraph G with a fixed planar straight-line convex
drawing, we consider the question whether this drawing can be extended to a planar
straight-line drawing of G. We characterize when this is possible in terms of simple
necessary conditions, which we prove to be sufficient. This also leads to a linear-time
testing algorithm. If a drawing extension exists, one can be computed in the same
running time.

http://dx.doi.org/10.1007/s00453-015-0018-6

http://publik.tuwien.ac.at/files/publik_257077.pdf