A linear-time algorithm for drawing a planar graph on a grid. (English) Zbl 0875.68452
Summary: We present a linear-time algorithm that, given an n-vertex planar graph G, finds an embedding of G into a \((2n-4)\times (n-2)\) grid such that the edges of G are straight-line segments.
MSC:
| 68W10 | Parallel algorithms in computer science |
Keywords:
AlgorithmsReferences:
| [1] | Booth, K. S.; Lueker, G. S., Testing for consecutive ones property, interval graphs and graph planarity testing using PQ-tree algorithms, J. Comput. System Sci., 13, 335-379 (1976) · Zbl 0367.68034 |
| [2] | Chiba, N.; Onoguchi, K.; Nishizeki, T., Drawing planar graphs nicely, Acta Inform., 22, 187-201 (1985) · Zbl 0545.68057 |
| [3] | Chiba, N.; Yamanouchi, T.; Nishizeki, T., Linear algorithms for convex drawings of planar graphs, (Bondy, J. A.; Murty, U. S.R., Progress in Graph Theory (1984), Academic Press: Academic Press New York), 153-173 · Zbl 0556.05023 |
| [4] | Chrobak, M.; Kant, G., Convex grid drawings of 3-connected planar graphs, (Tech. Rept. RUU-CS-93-45 (1993), Dept. of Computer Science, Utrecht University) |
| [5] | Chrobak, M.; Payne, T., A linear-time algorithm for drawing planar graphs on a grid, (Tech. Rept. UCR-CS-89-1 (1989), Dept. of Mathematics and Computer Science, University of California at Riverside) · Zbl 0875.68452 |
| [6] | Fáry, I., On straight lines representation of planar graphs, Acta. Sci. Math. Szeged, 11, 229-233 (1948) · Zbl 0030.17902 |
| [7] | de Fraysseix, H.; Pach, J.; Pollack, R., Small sets supporting Straight-Line Embeddings of planar graphs, (Proc. 20th Ann. Symp. on Theory of Computing (1988)), 426-433 |
| [8] | de Fraysseix, H.; Pach, J.; Pollack, R., How to draw a planar graph on a grid, Combinatorica, 10, 41-51 (1990) · Zbl 0728.05016 |
| [9] | Hopcroft, J.; Tarjan, R. E., Efficient planarity testing, J. ACM, 21, 549-568 (1974) · Zbl 0307.68025 |
| [10] | Jones, S.; Eades, P.; Moran, A.; Ward, N.; Delott, G.; Tamassia, R., A note on planar graph drawing algorithms, (Tech. Rept. 216 (1991), Dept. of Computer Science, University of Queensland) |
| [11] | Kant, G., Drawing planar graphs using the Imc-ordering, (Proc. 33rd Symp. on Foundations of Computer Science. Proc. 33rd Symp. on Foundations of Computer Science, Pittsburgh (1992)), 101-110 · Zbl 0918.68075 |
| [12] | Kant, G., Algorithms for drawing planar graphs, (Ph.D. Dissertation (1993), Dept. of Computer Science, University of Utrecht) · Zbl 0851.68086 |
| [13] | Rosenstiehl, P.; Tarjan, R. E., Rectilinear planar layouts and bipolar orientations of planar graphs, Discrete Comput. Geom., 1, 343-353 (1986) · Zbl 0607.05027 |
| [14] | Schnyder, W., Embedding planar graphs in the grid, (Proc. 1st Ann. ACM — SIAM Symp. on Discrete Algorithms. Proc. 1st Ann. ACM — SIAM Symp. on Discrete Algorithms, San Francisco (1990)), 138-147 · Zbl 0786.05029 |
| [15] | Schnyder, W.; Trotter, W., Convex drawings of planar graphs, Abstracts AMS, 13, 5 (1992), 92T-05-135 |
| [16] | Stein, S. K., Convex maps, (Proc. Amer. Math. Soc., 2 (1951)), 464-466 · Zbl 0042.42004 |
| [17] | Steinitz, E.; Rademacher, H., Vorlesungen über die Theorie Der Polyeder (1934), Springer: Springer Berlin · Zbl 0325.52001 |
| [18] | Tamassia, R.; Tollis, I. G., A unified approach to visibility representations of planar graphs, Discrete Comput. Geom., 1, 321-341 (1986) · Zbl 0607.05026 |
| [19] | Tutte, W. T., How to draw a graph, (Proc. London Math. Soc., 13 (1963)), 743-768 · Zbl 0115.40805 |
| [20] | Wagner, K., Bemerkungen zum vierfarbenproblem, Jahresberl. Deutsch. Math.-Verein., 46, 26-32 (1936) · Zbl 0014.18102 |
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.
