Product graph representations. (English) Zbl 0766.05092

Author’s abstract: We study a hierarchy of canonical representations of graphs as subgraphs of cartesian products of graphs. This hierarchy starts with the isometric representation, includes the 2-isometric representation, and ends with the cartesian prime factorization. We show that all three representations can be obtained in \(O(mn)\) time using \(O(m)\) space, for graphs with \(n\) vertices and \(m\) edges. The algorithms have immediate parallel versions that use \(n^ 3\) processors and run in \(O(\log^ 2n)\) time.


05C99 Graph theory
05C10 Planar graphs; geometric and topological aspects of graph theory
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI


[1] , and , The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, MA (1974).
[2] Aurenhammer, Discrete Math.
[3] , and Factoring cartesian product graphs at logarithmic cost per edge. Arbeitsbericht 2/1990, Montanuniversitaet Leoben, Austria (1990).
[4] Bandelt, J. Graph Theory 8 pp 501– (1984)
[5] Chung, Combinatorica 9 pp 111– (1989)
[6] and , Matrix multiplication via arithmetic progressions. Proceedings of the 19th ACM Symposium on Theory of Computing (1987) 1–6.
[7] Djokovič, J. Combinat. Theory B 14 pp 263– (1973)
[8] A new fixed point approach for stable networks and stable marriages. Proceedings of the 21st ACM Symposium on Theory of Computing (1989) 513–522.
[9] J. Comput. and Sys. Sci.
[10] Stable networks and product graphs. Ph.D. dissertation, Stanford University (1991) Technical Report STAN-CS-91-1362.
[11] Product graphs: some algorithmic and combinatorial results. Ph.D. thesis Stanford University, Stanford, California (1986) Report No. STAN-CS-86-1121.
[12] Feigenbaum, Discrete Appl. Math. 12 pp 123– (1985)
[13] Graph retractions. Colloq. Intern. Teorie Combinatorie II, Roma (1976) 263–268.
[14] Hell, Can. J. math. 39 pp 544– (1987) · Zbl 0627.05039
[15] Hochstrasser, Discrete Math.
[16] Graham, Trans. Am. Math. Soc. 288 pp 527– (1985)
[17] Graham, Bell System Tech. J. 50 pp 2495– (1971) · Zbl 0228.94020
[18] and , On embedding graphs in squashed cubes. Graph Theory and Applications, Lecture Nots No. 303, Springer-Verlag, Berlin (1972).
[19] , and , Implicit representation of graphs. Proceedings of the 28th ACM Symposium on Theory of Computing (1988) 334–343.
[20] Nowakowski, Combinatorica 2 pp 79– (1982)
[21] Nowakowski, Discrete Math. 43 pp 235–
[22] Sabidussi, Math. Zeitschr. 72 pp 446– (1960)
[23] Vizing, Vychislitel’nye Sistemy 9 pp 30– (1963)
[24] The complexity of parallel computations. Ph.D. thesis, Cornell University, Ithaca, NY (1979).
[25] Winkler, Eur. J. Combinat. 8 pp 209– (1987) · Zbl 0625.05050
[26] Winkler, London Math. Soc. Lecture Notes Series 123 pp 197– (1987)
[27] A simple algorithm for factoring a cartesian-product graph. Technical Report, Montanuniversität, Leoben.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.