
68 CHAPTER 2. CROSSINGS AND PLANARIZATION
The running time for incremental planar ity testing has been improved by La Poutr´e [La 94]
to O(α(|E|, |V |)) amortized time per query and update operation. This yields an almost
linear time algorithm for the maximal planar subgraph problem that runs in O(|V | + |E| ·
α(|E|, |V |)) time. Here, α(x, y) denotes the inverse Ackermann function, which means that
α(x, y) is a function that grows extremely slowly. A linear time algorithm for finding a max-
imal planar subgraph is given by Dji dj ev [Dji95 ] . This algorithm uses BC- and S PQ R-t r ee s
and applies a fast data structure for online planarity t es ti ...