Abstract
In this paper we consider the problems of testing a multi-level graph for planarity and laying out or, drawing, a multi-level graph in a clear way. We introduce a new abstraction of a common integer linear programming formulation of the problems that we call a vertex-exchange graph. We demonstrate how this concept can be used to solve the problems by providing clear and simple algorithms for testing a multi-level graph for planarity and laying out a multi-level graph when planar.
Original language | English |
---|---|
Pages (from-to) | 331-344 |
Number of pages | 14 |
Journal | Theoretical Computer Science |
Volume | 320 |
Issue number | 2-3 |
DOIs | |
Publication status | Published - 14 Jun 2004 |
Keywords
- Level graph layout
- Level graphs
- Level planarity testing