TY - GEN
T1 - Planarity-preserving clustering and embedding for large planar graphs?
AU - Duncan, Christian A.
AU - Goodrich, Michael T.
AU - Kobourov, Stephen G.
N1 - Funding Information:
✩ A preliminary version of this paper appeared in the Proceedings of the 7th Annual Symposium on Graph Drawing (GD ’99), 1999, pp. 186–196. This research was partially supported by NSF under grant CCR-9732300 and ARO under grant DAAH04-96-1-0013. * Corresponding author. E-mail addresses: duncan@cs.miami.edu (C.A. Duncan), goodrich@ics.uci.edu (M.T. Goodrich), kobourov@cs.arizona.edu (S.G. Kobourov).
Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1999.
PY - 1999
Y1 - 1999
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=22844454938&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=22844454938&partnerID=8YFLogxK
U2 - 10.1007/3-540-46648-7_19
DO - 10.1007/3-540-46648-7_19
M3 - Conference contribution
AN - SCOPUS:22844454938
SN - 3540669043
SN - 9783540669043
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 186
EP - 196
BT - Graph Drawing - 7th International Symposium, GD 1999, Proceedings
A2 - Kratochvil, Jan
PB - Springer-Verlag
T2 - 7th International Symposium on Graph Drawing, GD 1999
Y2 - 15 September 1999 through 19 September 1999
ER -