Visibility and Graph Drawing Research at the University of Lethbridge

ArrangePak, OrthoPak and VisPak are software packages written at the University of Lethbridge, in C++ and using LEDA (Library of Efficient Data types and Algorithms).

The VisPak package (now version 2) is useful for constructing the visibility graphs of: line segments (both endpoint visibility and bar-representations), orthogonal polygons, general polygons, and rectangles (with 2 lines of sight); algorithms for determining the visibility polygons of individual endpoints of line segments have also been implemented and include a demonstration of the depth-first spiralling technique. This ongoing project, which is funded through NSERC, is supervised by Dr. S. Wismath of the Dept. of Mathematics and Computer Science. Much of the initial coding was performed by H. Pinto in the summer of 1995 and the documentation and debugging was done by L. Jackson. Version 1.2 was written by L. Jackson in the spring and summer of 1996 and includes many improvements over the initial package. Version 2.0 includes the computation of the full visibility graph of a set of line segments and also the ability to interactively draw arrangements of lines and is now available. Coding was continued by M. Closson and S. Gartshore in the summer of 1998 and added to by John Johansen. In the summer of 2002, Ray Dufresne and Jon Wilsdon made a major upgrade creating version 2.02 of each package. This is the latest version.

A technical report including User's Manual in postscript form can be obtained:

ArrangePak is designed to aid researchers studying arrangements of lines and pseudo-lines and provides the interactive manipulation of arrangements, the associated wiring diagram, a simple duality transformation and a topologically equivalent pseudo-line arrangement. The coding was done by Closson and Gartshore in Summer 1998.

OrthoPak is a 3-d orthogonal drawing package that implements several algorithms for constructing 3-d VRML layouts of graphs which can then be viewed with a VRML browser (not supplied).

Please visit our DOWNLOAD PAGE.

This software is distributed free of charge for teaching and research purposes. If you use the software, please send us a note (and suggest improvements).

For more information please contact:
Dr. S. K. Wismath
Dept. of Mathematics and Computer Science,
University of Lethbridge,
Lethbridge, Alberta,