Optimal decremental connectivity in planar graphs

{\L}{\c{a}}cki, Jakub; Sankowski, Piotr
We show an algorithm for dynamic maintenance of connectivity information in an undirected planar graph subject to edge deletions. Our algorithm may answer connectivity queries of the form `Are vertices {\$}u{\$} and {\$}v{\$} connected with a path?' in constant time. The queries can be intermixed with any sequence of edge deletions, and the algorithm handles all updates in {\$}O(n){\$} time. This results improves over previously known {\$}O(n \backslashlog n){\$} time algorithm.
Research areas:
Year:
2014
Type of Publication:
Article
Keywords:
decremental connectivity; dynamic connectivity; planar graphs
Journal:
Theory Computer Systems
Volume:
3
Pages:
1-10
ISSN:
1868-8969
DOI:
10.4230/LIPIcs.STACS.2015.608
Hits: 3294

We use cookies to improve our website and your experience when using it. Cookies used for the essential operation of this site have already been set. To find out more about the cookies we use and how to delete them, see our privacy policy.

  I accept cookies from this site.
EU Cookie Directive Module Information