Graph Embedding with Minimum Depth and Maximum External Face (Extended Abstract)

Gutwenger, Carsten and Mutzel, Petra (2004) Graph Embedding with Minimum Depth and Maximum External Face (Extended Abstract). In: Graph Drawing 11th International Symposium, GD 2003, September 21-24, 2003 , pp. 259-272(Official URL: http://dx.doi.org/10.1007/978-3-540-24595-7_24).

Full text not available from this repository.

Abstract

We present new linear time algorithms using the SPQR-tree data structure for computing planar embeddings of planar graphs optimizing certain distance measures. Experience with orthogonal drawings generated by the topology-shape-metrics approach shows that planar embeddings following these distance measures lead to improved quality of the final drawing in terms of bends, edge length, and drawing area. Given a planar graph, the algorithms compute the planar embedding with 1. the minimum depth among the set of all planar embeddings of G, 2. the external face of maximum size among the set of all planar embeddings of G, 3. the external face of maximum size among the set of all embeddings of G with minimum depth.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-540-24595-7_24
Classifications: M Methods > M.800 Topology-shape-metrics
M Methods > M.600 Planar
G Algorithms and Complexity > G.490 Embeddings
G Algorithms and Complexity > G.560 Geometry
URI: http://gdea.informatik.uni-koeln.de/id/eprint/456

Actions (login required)

View Item View Item