License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-3430
URL: http://drops.dagstuhl.de/opus/volltexte/2006/343/

Harrigan, Martin ; Healy, Patrick

On Layering Directed Acyclic Graphs

pdf-format:
Dokument 1.pdf (199 KB)


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.

BibTeX - Entry

@InProceedings{harrigan_et_al:DSP:2006:343,
  author =	{Martin Harrigan and Patrick Healy},
  title =	{On Layering Directed Acyclic Graphs},
  booktitle =	{Graph Drawing},
  year =	{2006},
  editor =	{Michael J{\"u}nger  and Stephen Kobourov  and Petra Mutzel},
  number =	{05191},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2006/343},
  annote =	{Keywords: Graph Drawing, Hierarchical Drawings, Layerings, Minimum Dummy Nodes}
}

Keywords: Graph Drawing, Hierarchical Drawings, Layerings, Minimum Dummy Nodes
Seminar: 05191 - Graph Drawing
Issue date: 2006
Date of publication: 09.01.2006


DROPS-Home | Fulltext Search | Imprint Published by LZI