Planar orientations with low out-degree and compaction of adjacency matrices. (English) Zbl 0735.68015
A \(d\)-bounded orientation of an undirected graph is an orientation of its edges so that each vertex has outdegree at most \(d\). It is shown that planar graphs have 3-bounded orientations and they have 5-bounded acyclic orientations, both of which can be constructed in linear time. Parallel algorithms are given for finding 3-bounded orientations and 6-bounded acyclic orientations of planar graphs that do not require a planar embedding to be provided. Similar results are established for outerplanar and series-parallel graphs. Applications to compact data structures for representing planar graphs, using linear space but providing a constant time method for deciding adjacency of two vertices, are discussed.
Reviewer: C.J.Colbourn
References:
| [1] | Aho, A.; Hopcroft, J.; Ullman, J., The Design and Analysis of Computer Algorithms (1974), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0326.68005 |
| [2] | Bar-Yehuda, R.; Even, S., On approximating a vertex cover for planar graphs, Proc. 14th Ann. ACM Symp. on Theory of Computing, 303-309 (1982), San Francisco, CA |
| [3] | Brent, R. P., The parallel evaluation of general arithmetic expressions, J. Assoc. Comput. Mach., 21, 201-206 (1974) · Zbl 0276.68010 |
| [4] | Chiba, N.; Nishizeki, T.; Saito, N., An approximation algorithm for the maximum independent set problem on planar graphs, SIAM J. Comput., 663-675 (1982) · Zbl 0492.68051 |
| [5] | Chiba, N.; Nishizeki, T., Arboricity and subgraph listing algorithms, SIAM J. Comput., 14, 210-223 (1985) · Zbl 0572.68053 |
| [6] | M. Chrobak and J. Naor, An efficient parallel algorithm for computing a large independent set in planar graphs, Submitted for publication.; M. Chrobak and J. Naor, An efficient parallel algorithm for computing a large independent set in planar graphs, Submitted for publication. · Zbl 0731.68085 |
| [7] | K. Diks, Parallel recognition of outer-planar graphs, Submitted for publication.; K. Diks, Parallel recognition of outer-planar graphs, Submitted for publication. · Zbl 0633.68065 |
| [8] | D. Eppstein, Parallel recognition of series-parallel graphs, Submitted for publication.; D. Eppstein, Parallel recognition of series-parallel graphs, Submitted for publication. · Zbl 0754.68056 |
| [9] | Fleishner, H. J.; Geller, D. P.; Harary, F., Outerplanar graphs and weak duals, J. Indian Math. Soc., 38, 215-219 (1974) · Zbl 0352.05029 |
| [10] | Goldberg, A.; Plotkin, S.; Shannon, G., Parallel symmetry breaking in sparse graphs, Proc. 19th Ann. Symp. on Theory of Computing, 315-324 (1987) |
| [11] | T. Hagerup, M. Chrobak and K. Diks, Optimal parallel 5-coloring of planar graphs, SIAM J. Comput., to appear.; T. Hagerup, M. Chrobak and K. Diks, Optimal parallel 5-coloring of planar graphs, SIAM J. Comput., to appear. · Zbl 0688.68068 |
| [12] | Harary, F., Graph Theory (1972), Academic Press: Academic Press New York · Zbl 0797.05064 |
| [13] | He, X.; Yesha, Y., Parallel recognition and decomposition of two terminal series parallel graphs, Inform. and Comput., 75, 15-38 (1987) · Zbl 0636.68090 |
| [14] | Hopcroft, J. E.; Tarjan, R. E., Efficient planarity testing, J. Assoc. Comput. Mach., 21, 549-568 (1974) · Zbl 0307.68025 |
| [15] | Itai, A.; Rodeh, M., Finding a minimum circuit in a graph, SIAM J. Comput., 7, 413-423 (1978) · Zbl 0386.68064 |
| [16] | Kannan, S.; Naor, M.; Rudich, S., Implicit representations of graphs, Proc. 20th Ann. Symp. on Theory of Computing, 334-343 (1988) |
| [17] | Ladner, R. E.; Fischer, M. J., Parallel prefix computation, J. Assoc. Comput. Mach., 27, 831-838 (1980) · Zbl 0445.68066 |
| [18] | Nash-Williams, C., On orientations, connectivity and odd-vertex pairings in finite graphs, Can. J. Math., 12, 555-567 (1960) · Zbl 0096.38002 |
| [19] | Nash-Williams, C., Edge-disjoint spanning trees of finite graphs, J. London Math. Soc., 36, 445-450 (1961) · Zbl 0102.38805 |
| [20] | Papadimitriou, C.; Yannakakis, M., The clique problem for planar graphs, Inform. Process Lett., 13, 131-133 (1981) |
| [21] | W. Schnyder, Embedding planar graphs on the grids, a manuscript.; W. Schnyder, Embedding planar graphs on the grids, a manuscript. · Zbl 0786.05029 |
| [22] | Tarjan, R.; Vishkin, U., An efficient parallel biconnectivity algorithm, SIAM J. Comput., 14, 862-874 (1985) · Zbl 0575.68066 |
| [23] | Valdes, J.; Tarjan, R. E.; Lawler, E. L., The recognition of series parallel digraphs, Proc. 11th Ann. ACM Symp. on Theory of Computing, 1-12 (1979) |
| [24] | S. Vishwanathan and M.A. Sridhar, Some results on graph coloring in paralle, manuscript.; S. Vishwanathan and M.A. Sridhar, Some results on graph coloring in paralle, manuscript. |
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.
