Paper Info
Title
On the Parameterized Complexity of Layered Graph Drawing
Abstract
We consider graph drawings in which vertices are assigned to layers and edges are drawn as straight line-segments between vertices on adjacent layers. We prove that graphs admitting crossing-free h-layer drawings (for xed h) have bounded pathwidth. We then use a path decomposition as the basis for a linear-time algorithm to decide if a graph has a crossing-free h-layer drawing (for xed 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 crossing-free drawing (for xed k or r). If the number of crossings or deleted edges is a non-xed parameter then these problems are NP-complete. 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 so-called Sugiyama method for layered graph drawing, our algorithms do not assume a preassignment of the vertices to layers.
Year
DOI
Venue
2008
10.1007/s00453-007-9151-1
European Symposium on Algorithms
Keywords
DocType
Volume
crossing-free drawing,layered graph drawing,graph drawing,downward drawing,parameterized complexity,total span,fixed h,maximum span,crossing-free h-layer drawing,k crossing,fixed k,directed graph
Journal
52
Issue
ISSN
ISBN
2
0178-4617
3-540-42493-8
Citations 
PageRank 
References 
30
1.54
30
Authors
12
Name
Order
Citations
PageRank
Vida Dujmović121617.12
Michael R. Fellows24138319.37
Michael T. Hallett347942.87
Matthew Kitching4876.43
Giuseppe Liotta51356112.95
Catherine McCartin629620.26
Naomi Nishimura729219.82
Prabhakar Ragde852991.67
Frances A. Rosamond968434.52
Matthew Suderman1014210.03
Sue Whitesides111449197.63
David R. Wood12107396.22