@inproceedings{92cd875216264dc4bbfdccbeaf63f616,
title = "Facets of the directed acyclic graph layering polytope",
abstract = "The drawing of hierarchical graphs is one of the main areas of research in the field of Graph Drawing. In this paper we study the problem of partitioning the node set of a directed acyclic graph into layers-the first step of the commonly accepted Sugiyama algorithm for drawing directed acyclic graphs as hierarchies. We present a combinatorial optimization approach to the layering problem; we define a graph layering polytope and describe its properties in terms of facet-defining inequalities. The theoretical study presented is the basis of a new branch-and-cut layering algorithm which produces better quality drawings of hierarchical graphs.",
author = "Patrick Healy and Nikolov, {Nikola S.}",
year = "2002",
doi = "10.1007/3-540-36379-3_22",
language = "English",
isbn = "3540003312",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "246--257",
editor = "Ludek Kucera",
booktitle = "Graph-Theoretic Concepts in Computer Science - 28th International Workshop, WG 2002, Revised Papers",
note = "28th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2002 ; Conference date: 13-06-2002 Through 15-06-2002",
}