Abstract
We consider graph drawings in which vertices are assigned to layers and edges are drawn as straight linesegments between vertices on adjacent layers. We prove that graphs admitting crossingfree hlayer drawings (for fixed h) have bounded pathwidth. We then use a path decomposition as the basis for a lineartime algorithm to decide if a graph has a crossingfree hlayer drawing (for fixed h). This algorithm is extended to solve a large number of related problems, including allowing at most k crossings, or removing at most r edges to leave a crossingfree drawing (for fixed k or r). If the number of crossings or deleted edges is a nonfixed parameter then these problems are NPcomplete. For each setting, we can also permit downward drawings of directed graphs and drawings in which edges may span multiple layers, in which case the total span or the maximum span of edges can be minimized. In contrast to the socalled Sugiyama method for layered graph drawing, our algorithms do not assume a preassignment of the vertices to layers.
Original language  English 

Title of host publication  Algorithms  ESA 2001  9th Annual European Symposium, Proceedings 
Publisher  SpringerVerlag London Ltd. 
Pages  488499 
Number of pages  12 
ISBN (Print)  9783540424932 
Publication status  Published  1 Jan 2001 
Externally published  Yes 
Event  European Symposium on Algorithms 2001  Arhus, Denmark Duration: 28 Aug 2001 → 31 Aug 2001 Conference number: 9th https://link.springer.com/book/10.1007%2F3540446761 (Proceedings) 
Publication series
Name  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 

Volume  2161 
ISSN (Print)  03029743 
ISSN (Electronic)  16113349 
Conference
Conference  European Symposium on Algorithms 2001 

Abbreviated title  ESA 2001 
Country/Territory  Denmark 
City  Arhus 
Period  28/08/01 → 31/08/01 
Internet address 
