Duncan, Christian A. and Goodrich, Michael T. and Kobourov, Stephen G. (1999) Planarity-Preserving Clustering and Embedding for Large Planar Graphs. [Conference Paper]
Full text not available from this repository.
Abstract
In this paper we present a novel approach for cluster-based drawing of large planar graphs that maintains planarity. Our technique works for arbitrary planar graphs and produces a clustering which satisfies the conditions for compound-planarity (c-planarity). Using the clustering, we obtain a representation of the graph as a collection of O(log n) layers, where each succeeding layer represents the graph in an increasing level of detail. At the same time, the difference between two graphs on neighboring layers of the hierarchy is small, thus preserving the viewer's mental map. The overall running time of the algorithm is O(n log n), where n is the number of vertices of graph G.
| Item Type: | Conference Paper |
|---|---|
| Classifications: | G Algorithms and Complexity > G.490 Embeddings P Styles > P.180 Cluster M Methods > M.600 Planar G Algorithms and Complexity > G.350 Clusters P Styles > P.540 Planar |
| ID Code: | 327 |
| Deposited By: | Maciejak, Agnes |
| Deposited On: | 23 Nov 2004 |
| Last Modified: | 18 Sep 2008 13:08 |
| Alternative Locations: | http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=1731&spage=186 |
Repository Staff Only: item control page
