On Drawing a Graph Convexly in the Plane (Extended Abstract)

Djidjev, Hristo (1995) On Drawing a Graph Convexly in the Plane (Extended Abstract). In: Graph Drawing DIMACS International Workshop, GD 1994, October 10–12, 1994 , pp. 76-83(Official URL: http://dx.doi.org/10.1007/3-540-58950-3_358).

Full text not available from this repository.

Abstract

Let G be a planar graph and H be a subgraph of G. Given any convex drawing of H, we investigate the problem of how to extend the drawing of H to a convex drawing of G. We obtain a necessary and sufficient condition for the existence and a linear algorithm for the construction of such an extension. Our results and their corollaries generalize previous theoretical and algorithmic results of Tutte, Thomassen, Chiba, Yamanouchi, and Nishizeki.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-58950-3_358
Classifications: M Methods > M.999 Others
Z Theory > Z.250 Geometry
G Algorithms and Complexity > G.999 Others
M Methods > M.600 Planar
P Styles > P.540 Planar
URI: http://gdea.informatik.uni-koeln.de/id/eprint/100

Actions (login required)

View Item View Item