On Layering Directed Acyclc Graphs

Martin Harrigan, Patrick Healy

Research output: Contribution to journalConference articlepeer-review


We consider the problem of layering a directed acyclic graph with minimum dummy nodes. We present a new Integer Linear Programming formulation of the problem based on a set of fundamental cycles in the underlying undirected graph and show that it can be solved in polynomial time. We outline some of the advantages of the formulation. Each solution defines a family of layerings with the same number of dummy nodes. We can also transform one solution into another by adding or removing certain combinations of dummy nodes, thus allowing the consideration of other aesthetics.

Original languageEnglish
JournalDagstuhl Seminar Proceedings
Publication statusPublished - 2006
Externally publishedYes
EventGraph Drawing 2005 - Wadern, Germany
Duration: 08 May 200513 May 2005


Dive into the research topics of 'On Layering Directed Acyclc Graphs'. Together they form a unique fingerprint.

Cite this