DagSemProc.05191.6.pdf
- Filesize: 198 kB
- 11 pages
Document
On Layering Directed Acyclic Graphs
Authors
-
Part of:
Volume:
Dagstuhl Seminar Proceedings, Volume 5191
Series: Dagstuhl Seminar Proceedings (DagSemProc) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2006-01-09
Cite As Get BibTex
Martin Harrigan and Patrick Healy. On Layering Directed Acyclic Graphs. In Graph Drawing. Dagstuhl Seminar Proceedings, Volume 5191, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)
https://doi.org/10.4230/DagSemProc.05191.6
Abstract
We consider the problem of layering a directed acyclic graph with minimum dummy nodes. We present a new Integer Linear Programming (ILP) 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.
Subject Classification
Keywords
- Graph Drawing
- Hierarchical Drawings
- Layerings
- Minimum Dummy Nodes
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads