2026-08-10T07:42:41Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:343 2024-03-06T11:06:23Z ddc:004 open_access

On Layering Directed Acyclic Graphs Harrigan, Martin Healy, Patrick Graph Drawing Hierarchical Drawings Layerings Minimum Dummy Nodes 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Martin Harrigan and Patrick Healy 2006 Is Part Of Dagstuhl Seminar Proceedings, Volume 5191, Graph Drawing (2006) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.05191.6 urn:nbn:de:0030-drops-3430 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05191.6 eng https://creativecommons.org/licenses/by/4.0/legalcode