Partitioned Drawings

Siebenhaller, Martin (2007) Partitioned Drawings. In: Graph Drawing 14th International Symposium, GD 2006, September 18-20, 2006, Karlsruhe, Germany , pp. 252-257 (Official URL:

Full text not available from this repository.


In this paper we consider the problem of creating partitioned drawings of graphs G=(V,E). In a partitioned drawing each vertex is placed inside a given partition cell of a rectangular partition of the drawing area. This problem has several applications in practice, e.g. for UML activity diagrams or wiring schematics. We first formalize the problem and analyze its complexity. Then we give a heuristic approach which is based on the topology-shape-metrics approach and produces partitioned drawings in time O((|V|+c)^2 log (|V|+c)), where c denotes the number of crossings.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-70904-6_25
Classifications:G Algorithms and Complexity > G.350 Clusters
J Applications > J.999 Others
ID Code:780

Repository Staff Only: item control page


U. Brandes, M. Eiglsperger, M. Kaufmann, and D. Wagner. Sketch-driven orthogonal graph drawing. In Proceedings of the 10th International Symposium on Graph Drawing (GD'02), volume 2528 of LNCS, pages 1-12. Springer, 2002.

G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall, 1999.

M. Eiglsperger. Automatic Layout of UML Class Diagrams: A Topology-Shape-Metrics Approach. PhD thesis, Universitat Tubingen, 2003.

M. Eiglsperger, M. Siebenhaller, and M. Kaufmann. An ecient implementation of Sugiyama's algorithm for layered graph drawing. In Proceedings of the 12th Symposium on Graph Drawing (GD'04), volume 3383 of LNCS, pages 155-166. Springer, 2005.

U. Fomeier and M. Kaufmann. Drawing high degree graphs with low bend numbers. In Proceedings of the 3rd International Symposium on Graph Drawing (GD'95), volume 1027 of LNCS, pages 254-266. Springer, 1996.

M. R. Garey and D. S. Johnson. Crossing number is NP-complete. SIAM Journal on Algebraic and Discrete Methods, 4:312-316, 1983.

J. E. Hopcroft and R. E. Tarjan. Ecient planarity testing. Journal of the ACM, 21(4):549-568, 1974.

J. Pach and R. Wenger. Embedding planar graphs at xed vertex locations. In Proceedings of the 6th Symposium on Graph Drawing (GD'98), volume 1547 of LNCS, pages 263-274. Springer, 1998.

M. Siebenhaller and M. Kaufmann. Mixed upward planarization - fast and robust. In Proceedings of the 13th Symposium on Graph Drawing (GD'05), volume 3843 of LNCS, pages 522-523. Springer, 2006.

yWorks. yFiles - a java graph layout and visualization library (WWW document). (accessed September 2006).