Drawing Planar Graphs with a Prescribed Inner FaceMchedlidze, Tamara and Nöllenburg, Martin and Rutter, Ignaz (2013) Drawing Planar Graphs with a Prescribed Inner Face. In: 21st International Symposium, GD 2013, September 23-25, 2013 , pp. 316-327(Official URL: http://dx.doi.org/10.1007/978-3-319-03841-4_28). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/978-3-319-03841-4_28
AbstractGiven a plane graph G (i.e., a planar graph with a fixed planar embedding) and a simple cycle C in G whose vertices are mapped to a convex polygon, 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, it can be computed in the same running time.
Actions (login required)
|