[author]Adam Buchsbaum, Emden Gansner, Suresh Venkatasubramanian[/author]
2007 Asia-Pacific Symposium on Visualisation
This paper deals with the problem, arising in practice, of drawing a directed graph as a collection of disjoint, isothetic rectangles, where the rectangles of the nodes of each edge must touch and where the placement of the rectangles respects the ordering of the edges. It provides characterizations for those graphs having the special type of rectangular layout known as a rectangular dual. It then characterizes the st-graphs having rectangular layouts in terms of the existence of certain planar embeddings and the non-existence of a particular subgraph.

Links: PDF (87 K) // BibTeX