The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 25 NO.5 / (1996))
On-Line Planarity Testing
Giuseppe Di Battista, Roberto Tamassia,
Pages. 956-997
Abstract The on-line planarity-testing problem consists of performing the following operations on a planar graph $G$: (i) testing if a new edge can be added to $G$ so that the resulting graph is itself planar; (ii) adding vertices and edges such that planarity is preserved. An efficient technique for on-line planarity testing of a graph is presented that uses $O(n)$ space and supports tests and insertions of vertices and edges in $O(log n)$ time, where $n$ is the current number of vertices of $G$. The bounds for tests and vertex insertions are worst-case and the bound for edge insertions is amortized. We also present other applications of this technique to dynamic algorithms for planar graphs.
Contents 1. Introduction
2. Dynamic graph algorithms
3. Preliminaries
4. Tests
4.1. Decomposition tree
4.2. Test algorithm
4.3. Static data structure and time complexity
5. Updates
6. Dynamic data structure
6.1. Requirements
6.2. Maintaining planar embeddings
6.3. Data structure
6.4. Complexity analysis
7. Tests and updates in general graphs
7.1. Tests in connected graphs
7.2. Updates in connected graphs
8. Some applications
8.1. Graph planarization
8.2. Transitive closure
8.3. Minimum spanning tree
Key words planar graph, on-line algorithm, dynamic algorithm.
Mathmatical Subject Classification 68R10, 05C10, 68Q20, 68P05