Drawing Planar Graphs with a Prescribed Inner Face

Mchedlidze, 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.

Abstract

Given 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.

Item Type:	Conference Paper
Classifications:	P Styles > P.540 Planar P Styles > P.720 Straight-line
URI:	http://gdea.informatik.uni-koeln.de/id/eprint/1385

Actions (login required)

View Item