In this paper we deal with making drawings of clustered hierarchical graphs nicer. Given a planar graph G¿=¿(V,E) with an assignment of the vertices to horizontal layers, a plane drawing of G (with y-monotone edges) can be specified by stating for each layer the order of the vertices lying on and the edges intersecting that layer. Given these orders and a recursive partition of the vertices into clusters, we want to draw G such that (i) edges are straight-line segments, (ii) clusters lie in disjoint convex regions, (iii) no edge intersects a cluster boundary twice.
First we investigate fast algorithms that produce drawings of the above type if the clustering fulfills certain conditions. We give two fast algorithms with different preconditions. Second we give a linear programming (LP) formulation that always yields a drawing that fulfills the above three requirements—if such a drawing exists. The size of our LP formulation is linear in the size of the graph.
|Title of host publication||Proceedings of the 33rd Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2007) 20-26 January 2007, Harrachov, Czech Republic|
|Editors||J. Leeuwen, van, G.F. Italiano, W. Hoek, van der, C. Meinel, H. Sack, F. Plasil|
|Place of Publication||Berlin|
|Publication status||Published - 2007|
|Event||conference; (SOFSEM 2007), Harrachov, Czech Republic; 2007-01-20; 2007-01-26 - |
Duration: 20 Jan 2007 → 26 Jan 2007
|Name||Lecture Notes in Computer Science|
|Conference||conference; (SOFSEM 2007), Harrachov, Czech Republic; 2007-01-20; 2007-01-26|
|Period||20/01/07 → 26/01/07|
|Other||(SOFSEM 2007), Harrachov, Czech Republic|