Drawing plane graphs nicely. (English) Zbl 0545.68057

This paper presents two efficient algorithms for drawing plane graphs nicely. Both draw all edges of a graph as straight line segments without crossing lines. The first draws a plane graph ”convex” if possible, that is, in a way that every inner face and the complement of the outer face are convex polygons. The second, using the first, procedures a pleasing of a given plane graph that satisfies the following property as far as possible: the complements of 3-connected components, together with inner faces and the complement of the outer face, are convex polygons. The running time and storage space of both algorithms are linear in the number of vertices of the graph.


68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
05C10 Planar graphs; geometric and topological aspects of graph theory
Full Text: DOI


[1] Chiba, N., Nishizeki, T., Abe, S., Ozawa, T.: A linear algorithm for embedding planar graphs using PQ-trees. J. Comput. Syst. Sci. (To appear) · Zbl 0605.68060
[2] Chiba, N.; Yamanouchi, T.; Nishizeki, T.; Bondy, J. A.; Murty, U. S.R., Linear algorithms for convex drawings of planar graphs, Progress in Graph Theory, 153-173 (1984), Toronto: Academic Press, Toronto · Zbl 0556.05023
[3] Fary, I., On straight representations of planar graphs, Acta Sci. Math. Szeged, 11, 229-233 (1948) · Zbl 0030.17902
[4] Hopcroft, J. E.; Tarjan, R. E., Dividing a graph into triconnected components, SIAM J. Comput., 2, 135-158 (1973) · Zbl 0281.05111 · doi:10.1137/0202012
[5] Hopcroft, J. E.; Tarjan, R. E., Efficient planarity testing, J. ACM, 21, 549-568 (1974) · Zbl 0307.68025 · doi:10.1145/321850.321852
[6] Lipton, R. J.; Rose, D. J.; Tarjan, R. E., Generalized nested dissection, SIAM J. Numer. Anal., 16, 346-358 (1979) · Zbl 0435.65021 · doi:10.1137/0716027
[7] Reingold, E. M.; Tilford, J. S., Tidier drawings of trees, IEEE Trans. Software Eng., 3, 223-228 (1981) · doi:10.1109/TSE.1981.234519
[8] Supowit, K. J.; Reingold, E. M., The complexity of drawing trees nicely, Acta Inf., 18, 377-392 (1983) · Zbl 0493.68038 · doi:10.1007/BF00289576
[9] Thomassen, C., Planarity and duality of finite and infinite graphs, J. Comb. Theory, Ser. B, 29, 244-271 (1980) · Zbl 0441.05023 · doi:10.1016/0095-8956(80)90083-0
[10] Tutte, W. T., Convex representations of graphs, Proc. Lond. Math. Soc., 10, 3, 304-320 (1960) · Zbl 0094.36301 · doi:10.1112/plms/s3-10.1.304
[11] Tutte, W. T., How to draw a graph, Proc. Lond. Math. Soc., 13, 743-768 (1963) · Zbl 0115.40805 · doi:10.1112/plms/s3-13.1.743
[12] Vaucher, J. G., Pretty-printing of trees, Software, Pract. Exper., 10, 553-561 (1980) · Zbl 0431.68040 · doi:10.1002/spe.4380100706
[13] Wetherell, C.; Shannon, A., Tidy drawings of trees, IEEE Trans. Software Eng., 5, 514-520 (1970) · Zbl 0412.68092
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.