DATA-STRUCTURES FOR 2-EDGE CONNECTIVITY IN PLANAR GRAPHS

Authors
HERSHBERGER J RAUCH M SURI S
Citation
J. Hershberger et al., DATA-STRUCTURES FOR 2-EDGE CONNECTIVITY IN PLANAR GRAPHS, Theoretical computer science, 130(1), 1994, pp. 139-161
Citations number
19
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
Journal title
Theoretical computer science → ACNP
ISSN journal
03043975
Volume
130
Issue
1
Year of publication
1994
Pages
139 - 161
Database
ISI
SICI code
0304-3975(1994)130:1<139:DF2CIP>2.0.ZU;2-5
Abstract
We present a data structure for maintaining 2-edge connectivity inform ation dynamically in an embedded planar graph. The data structure requ ires linear storage and preprocessing time for its construction, suppo rts online updates (deletion of an edge or insertion of an edge consis tent with the embedding) in O(log2 n) time, and answers a query (wheth er two vertices are in the same 2-edge-connected component) in O(log n ) time. The previous best algorithm for this problem requires O(log3 n ) time for updates.