Straightening drawings of clustered hierarchical graphs

S. Bereg, M. Völker, A. Wolff, Y. Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review


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.
Original languageEnglish
Title of host publicationProceedings of the 33rd Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2007) 20-26 January 2007, Harrachov, Czech Republic
EditorsJ. Leeuwen, van, G.F. Italiano, W. Hoek, van der, C. Meinel, H. Sack, F. Plasil
Place of PublicationBerlin
ISBN (Print)978-3-540-69506-6
Publication statusPublished - 2007
Eventconference; (SOFSEM 2007), Harrachov, Czech Republic; 2007-01-20; 2007-01-26 -
Duration: 20 Jan 200726 Jan 2007

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Conferenceconference; (SOFSEM 2007), Harrachov, Czech Republic; 2007-01-20; 2007-01-26
Other(SOFSEM 2007), Harrachov, Czech Republic

Fingerprint Dive into the research topics of 'Straightening drawings of clustered hierarchical graphs'. Together they form a unique fingerprint.

Cite this