Fully dynamic planarity testing with applications.

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, w...

詳細記述

書誌詳細

出版年:	Journal of the ACM 46, 1 (1999).
第一著者:	Galil, Zvi
フォーマット:	論文
言語:	English
主題:	Theory of computation. Analysis of algorithms and problem complexity. Mathematics of computing. Discrete mathematics. Algorithms.