Algorithms for multi-level graph planarity testing and layout

Patrick Healy, Ago Kuusik

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
Pages (from-to)331-344
Number of pages14
JournalTheoretical Computer Science
Volume320
Issue number2-3
DOIs
Publication statusPublished - 14 Jun 2004

Keywords

  • Level graph layout
  • Level graphs
  • Level planarity testing

Fingerprint

Dive into the research topics of 'Algorithms for multi-level graph planarity testing and layout'. Together they form a unique fingerprint.

Cite this