Fully dynamic planarity testing with applications

ABSTRACT

This paper introduces compressed certificates for planarity, biconnectivity and triconnectivity in planar graphs, and proves many structural properties of certificates in planar graphs. As an application of our compressed certificates, we develop efficient dynamic planar algorithms. In particular, we consider the following three operations on a planar graph G: (i) insert an edge if the resultant graph remains planar; (ii) delete an edge; and (iii) test whether an edge could be added to the graph without violating planarity. We show how to support each of the above operations in O(n2/3) time, where n is the number of vertices in the graph. The bound for tests and deletions is worst-case, while the bound for insertions is amortized. This is the first algorithm for this problem with sub-linear running time, and it affirmatively answers a question posed in Epstein et al. [1992]. We use our compressed certificates for biconnectivity and triconnectivity to maintain the biconnected and triconnected components of a dynamic planar graph. The time bounds are the same: O(n2/3) worst-case time per edge deletion, O(n2/3) amortized time per edge insertion, and O(n2/3) amortized time per edge insertion, and O(n2/3)worst-case time to check whether two vertices are either biconnected or triconnected.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Giorgio Ausiello , Giuseppe F. Italiano , Alberto Marchetti Spaccamela , Umberto Nanni, Incremental algorithms for minimal length paths, Journal of Algorithms, v.12 n.4, p.615-638, Dec. 1991 [doi>10.1016/0196-6774(91)90036-X]
• 3: Daniel Bienstock , Clyde L. Monma, On the complexity of covering vertices by faces in a planar graph, SIAM Journal on Computing, v.17 n.1, p.53-76, Feb. 1988 [doi>10.1137/0217004]
• 4: BOOTH, K. S., AND LUEKER, G.S. 1976. Testing the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci. 13, 335-379.
• 5: Joseph Cheriyan , Ming-Yang Kao , Ramakrishna Thurimella, Scan-first search and sparse certificates: an improved parallel algorithm for k-vertex connectivity, SIAM Journal on Computing, v.22 n.1, p.157-174, Feb. 1993 [doi>10.1137/0222013]
• 6: J. Cheriyan , S. N. Maheshwari, Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs, Journal of Algorithms, v.9 n.4, p.507-537, Dec. 1988 [doi>10.1016/0196-6774(88)90015-6]
• 7: Robert F. Cohen , Roberto Tamassia, Dynamic expression trees and their applications, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.52-61, January 28-30, 1991, San Francisco, California, United States
• 8: DANTZIG, G. B., AND FULKERSON, D.R. 1956. On the max-flow min-cut theorem of networks. Ann. Math. Study 38, 215-221.
• 9: DI BATTISTA, G., AND TAMASSIA, R. 1989. Incremental planarity testing. In Proceedings of the 30th IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 436-441.
• 10: Giuseppe Di Battista , Roberto Tamassia, On-line graph algorithms with SPQR-trees, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.598-611, July 1990, Warwick University, England
• 11: EDMONDS, J. 1960. A combinatorial representation for polyhedral surfaces. Not. Am. Math Soc. 7, 646.
• 12: David Eppstein , Zvi Galil , Giuseppe F. Italiano , Amnon Nissenzweig, Sparsification—a technique for speeding up dynamic graph algorithms, Journal of the ACM (JACM), v.44 n.5, p.669-696, Sept. 1997 [doi>10.1145/265910.265914]
• 13: David Eppstein , Zvi Galil , Giuseppe F. Italiano , Thomas H. Spencer, Separator based sparsification I.: planarity testing and minimum spanning trees, Journal of Computer and System Sciences, v.52 n.1, p.3-27, Feb. 1996 [doi>10.1006/jcss.1996.0002]
• 14: David Eppstein , Zvi Galil , Giuseppe F. Italiano , Thomas H. Spencer, Separator-Based Sparsification II: Edge and Vertex Connectivity, SIAM Journal on Computing, v.28 n.1, p.341-381, Feb. 1999 [doi>10.1137/S0097539794269072]
• 15: David Eppstein , Giuseppe F. Italiano , Roberto Tamassia , Robert E. Tarjan , Jeffery Westbrook, Maintenance of a minimum spanning forest in a dynamic plane graph, Journal of Algorithms, v.13 n.1, p.33-54, March 1992 [doi>10.1016/0196-6774(92)90004-V]
• 16: Shimon Even, Graph Algorithms, W. H. Freeman & Co., New York, NY, 1979
• 17: EVEN, S., AND GAZIT, H. 1985. Updating distances in dynamic graphs. Meth. Oper. Res. 49, 371-387.
• 18: Shimon Even , Gene Itkis , Sergio Rajsbaum, On mixed connectivity certificates, Selected papers from the third European symposium on Algorithms, p.253-269, August 1998, Courfu, Greece
• 19: Yossi Shiloach , Shimon Even, An On-Line Edge-Deletion Problem, Journal of the ACM (JACM), v.28 n.1, p.1-4, Jan. 1981 [doi>10.1145/322234.322235]
• 20: EVEN, S., AND TARJAN, R.E. 1976. Computing an st-numbering. Theor. Comput. Sci. 2, 339-344.
• 21: FORTUNE, S. 1987. A sweepline algorithm for Voronoi diagrams. Algorithmica 2, 153-174.
• 22: András Frank , Toshihide Ibaraki , Hiroshi Nagamochi, On sparse subgraphs preserving connectivity properties, Journal of Graph Theory, v.17 n.3, p.275-281, July 1993 [doi>10.1002/jgt.3190170302]
• 23: FREDERICKSON, G.N. 1985. Data structures for on-line updating of minimum spanning trees. SIAM J. Comput. 14, 781-798.
• 24: Greg N. Frederickson, Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees, SIAM Journal on Computing, v.26 n.2, p.484-538, April 1997 [doi>10.1137/S0097539792226825]
• 25: Harold N. Gabow, Applications of a poset representation to edge connectivity and graph rigidity, Proceedings of the 32nd annual symposium on Foundations of computer science, p.812-821, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185453]
• 26: Harold N. Gabow, A matroid approach to finding edge connectivity and packing arborescences, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.112-122, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103436]
• 27: Harold N. Gabow , Matthias Stallmann, Efficient Algorithms for Graphic Intersection and Parity (Extended Abstract), Proceedings of the 12th Colloquium on Automata, Languages and Programming, p.210-220, July 15-19, 1985
• 28: Zvi Galil , Giuseppe F. Italiano, Maintaining biconnected components of dynamic planar graphs (extended abstract), Proceedings of the 18th international colloquium on Automata, languages and programming, p.339-350, June 1991, Madrid, Spain
• 29: Zvi Galil , Giuseppe F. Italiano, Fully dynamic algorithms for 2-edge connectivity, SIAM Journal on Computing, v.21 n.6, p.1047-1069, Dec. 1992 [doi>10.1137/0221062]
• 30: Zvi Galil , Giuseppe F. Italiano, Maintaining the 3-edge-connected components of a graph on-line, SIAM Journal on Computing, v.22 n.1, p.11-28, Feb. 1993 [doi>10.1137/0222002]
• 31: Zvi Galil , Giuseppe F. Italiano , Neil Sarnak, Fully dynamic planarity testing (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.495-506, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129761]
• 32: GIAMMARRESI, D., AND ITALIANO, G.F. 1996. Dynamic 2- and 3-connectivity on planar graphs. Algorithica 16, 3, 263-287.
• 33: HARARY, F. 1969. Graph Theory. Addison-Wesley, Reading, Mass.
• 34: M. R. Henzinger , V. King, Fully dynamic biconnectivity and transitive closure, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.664, October 23-25, 1995
• 35: Monika Rauch Henzinger , Valerie King, Randomized dynamic graph algorithms with polylogarithmic time per operation, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.519-527, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225269]
• 36: Monika Rauch Henzinger , Johannes A. La Poutré, Certificates and Fast Algorithms for Biconnectivity in Fully-Dynamic Graphs, Proceedings of the Third Annual European Symposium on Algorithms, p.171-184, September 25-27, 1995
• 37: HOLM, J., DE LICHTENBERG, K., AND THORUP, M. 1997. Polyalgorithmic deterministic fullydynamic graph algorithms II: 2-edge and biconnectivity. Tech. Rep. DIKU-TR-97/26 (Nov.). Dept. Comput. Sci., Univ. Copenhagen, Copenhagen, Sweden.
• 38: HOPCROFT, J., AND TARJAN, R.E. 1973. Dividing a graph into triconnected components. SIAM J. Comput. 2, 135-158.
• 39: John Hopcroft , Robert Tarjan, Efficient Planarity Testing, Journal of the ACM (JACM), v.21 n.4, p.549-568, Oct. 1974 [doi>10.1145/321850.321852]
• 40: IBARAKI, f., AND KATOH, N. 1983. On-line computation of transitive closure for graphs. Inf. Proc. Lett. 16, 95-97.
• 41: Alon Itai , Michael Rodeh, The multi-tree approach to reliability in distributed networks, Information and Computation, v.79 n.1, p.43-59, October 1988 [doi>10.1016/0890-5401(88)90016-8]
• 42: G. F. Italiano, Amortized efficiency of a path retrieval data structure, Theoretical Computer Science, v.48 n.2-3, p.273-281, Dec., 1986
• 43: Giuseppe F. Italiano, Finding paths and deleting edges in directed acyclic graphs, Information Processing Letters, v.28 n.1, p.5-11, May 30, 1988 [doi>10.1016/0020-0190(88)90136-6]
• 44: Arkady Kanevsky , Roberto Tamassia , Giuseppe Di Battista , Jianer Chen, On-line maintenance of the four-components of a graph (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.793-801, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185451]
• 45: Sanjeev Khanna , Rajeev Motwani , Randall H. Wilson, On certificates and lookahead in dynamic graph problems, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.222-231, January 28-30, 1996, Atlanta, Georgia, United States
• 46: Philip N. Klein , John H. Reif, An efficient parallel algorithm for planarity, Journal of Computer and System Sciences, v.37 n.2, p.190-246, October 1988 [doi>10.1016/0022-0000(88)90006-2]
• 47: Philip N. Klein , Sairam Subramanian, A Fully Dynamic Approximation Scheme for All-Pairs Shortest Paths in Planar Graphs, Proceedings of the Third Workshop on Algorithms and Data Structures, p.442-451, August 11-13, 1993
• 48: KURATOWSKI, C. 1930. Sur les problemes des courbes gauches en Topologie. Fund. Math. 16, 217-283.
• 49: LA POUTRI#, J.A. 1991. Dynamic graph algorithms and data structures. Ph.D. dissertation. Dept. Comput. Sci., Utrecht Univ.
• 50: J. A. La Poutré , J. van Leeuwen, Maintenance of transitive closures and transitive reductions of graphs, Proceedings of the International Workshop WG '87 on Graph-theoretic concepts in computer science, p.106-120, July 1988, Kloster Banz/Staffelstein, Germany
• 51: LEMPEL, A., EVEN, S., AND CEDERBAUM, I. 1967. An algorithm for planarity testing of graphs. In Theory of Graphs: International Symposium (Rome, Italy). Gordon and Breach, New York, pp. 215-232.
• 52: Chih-Chung Lin , Ruei-Chuan Chang, On the dynamic shortest path problem, Journal of Information Processing, v.13 n.4, p.470-476, 1990
• 53: LIPTON, R. J., AND TARJAN, R.E. 1979. A separator theorem for planar graphs. SIAM J. Appl. Math. 36, 177-189.
• 54: LIPTON, R.J., AND TARJAN, R.E. 1980. Applications of a planar separator theorem. SIAM J. Comput. 9, 615-627.
• 55: NAGAMOCHI, H., AND IBARAKI, T. 1992. Linear time algorithms for finding a sparse k-connected spanning subgraph of a k-connected graph. Algorithmica 7, 583-596.
• 56: RAMACHANDRAN, V., AND REIF, J.H. 1989. An optimal parallel algorithm for graph planarity. In Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 282-287.
• 57: Monika Rauch, Improved data structures for fully dynamic biconnectivity, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.686-695, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195434]
• 58: RAUCH, M.H. 1995. Fully dynamic biconnectivity in graphs. Algorithmica 13, 6 (June), 503-538.
• 59: John H. Reif, A topological approach to dynamic graph connectivity, Information Processing Letters, v.25 n.1, p.65-70, 20 April 1987 [doi>10.1016/0020-0190(87)90095-0]
• 60: H Rohnert, A dynamization of the all pairs least cost path problem, Proceedings on STACS 85 2nd annual symposium on theoretical aspects of computer science, p.279-286, December 1985, Saarbru:9Aicken, Germany
• 61: Roberto Tamassia, A Dynamic Data Structure for Planar Graph Embedding (Extended Abstract), Proceedings of the 15th International Colloquium on Automata, Languages and Programming, p.576-590, July 11-15, 1988
• 62: TAMASSIA, R., AND PREPARATA, f.P. 1990. Dynamic maintenance of planar digraphs, with applications. Algorithmica 5, 509-527.
• 63: TARJAN, R.E. 1972. Depth-first search and linear graph algorithms. SIAM J. Comput. 1, 146-160.
• 64: Ramakrishna Thurimella , Donald S. Fussell, Techniques for the design of parallel graph algorithms, 1989
• 65: TUTTE, W.f. 1966. Connectivity in Graphs. University of Toronto Press, Toronto, Ont., Canada.
• 66: TUTTE, W.f. 1984. Graph Theory. Cambridge University Press, Cambridge, England.
• 67: Jeffery Westbrook, Fast Incremental Planarity Testing, Proceedings of the 19th International Colloquium on Automata, Languages and Programming, p.342-353, July 13-17, 1992
• 68: J. Westbrook , R. E. Tarjan, Amortized analysis of algorithms for set union with backtracking, SIAM Journal on Computing, v.18 n.1, p.1-11, Feb. 1989 [doi>10.1137/0218001]
• 69: WHITNEY, H. 1930. Non-separable and planar graphs. Trans. Amer. Math Soc. 34, 339-362.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms

Keywords:
dynamic graph algorithms, planar graphs, planarity testing