Linear algorithms for convex drawings of planar graphs. (English) Zbl 0556.05023
Progress in graph theory, Proc. Conf. Combinatorics, Waterloo/Ont. 1982, 153-173 (1984).
[For the entire collection see Zbl 0546.00007.]
W. T. Tutte [Proc. Lond. Math. Soc., III. Ser. 10, 304-320 (1960; Zbl 0094.363)] gave a necessary and sufficient condition for a planar graph to have a convex representation such that a prescribed cycle is the outer polygon. The present paper contains a linear algorithm for drawing a graph such that all faces are bounded by convex polygons if such a drawing exists and also it contains a linear algorithm for finding those cycles which can play the role of the outer polygon in a convex drawing. These algorithms are based on the reviewer’s extension [J. Comb. Theory, Ser. B 29, 244-271 (1980; Zbl 0441.05023)] of Tutte’s result.
W. T. Tutte [Proc. Lond. Math. Soc., III. Ser. 10, 304-320 (1960; Zbl 0094.363)] gave a necessary and sufficient condition for a planar graph to have a convex representation such that a prescribed cycle is the outer polygon. The present paper contains a linear algorithm for drawing a graph such that all faces are bounded by convex polygons if such a drawing exists and also it contains a linear algorithm for finding those cycles which can play the role of the outer polygon in a convex drawing. These algorithms are based on the reviewer’s extension [J. Comb. Theory, Ser. B 29, 244-271 (1980; Zbl 0441.05023)] of Tutte’s result.
Reviewer: C.Thomassen
MSC:
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 52Bxx | Polytopes and polyhedra |
