Business Intelligence

Directed Graphs and Rectangular Layouts (Extended Abstract)

Download Now Free registration required

Executive Summary

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.

  • Format: PDF
  • Size: 86.5 KB