On the parameterized complexity of layered graph drawing

V. Dujmović, M. Fellows, M. Hallett, M. Kitching, G. Liotta, C. McCartin, N. Nishimura, P. Ragde, F. Rosamond, M. Suderman, S. Whitesides, D. R. Wood

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

31 Citations (Scopus)

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 fixed 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 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 crossing-free drawing (for fixed k or r). If the number of crossings or deleted edges is a non-fixed 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.

Original languageEnglish
Title of host publicationAlgorithms - ESA 2001 - 9th Annual European Symposium, Proceedings
PublisherSpringer-Verlag London Ltd.
Pages488-499
Number of pages12
ISBN (Print)9783540424932
Publication statusPublished - 1 Jan 2001
Externally publishedYes
EventEuropean Symposium on Algorithms 2001 - Arhus, Denmark
Duration: 28 Aug 200131 Aug 2001
Conference number: 9th
https://link.springer.com/book/10.1007%2F3-540-44676-1 (Proceedings)

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2161
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceEuropean Symposium on Algorithms 2001
Abbreviated titleESA 2001
Country/TerritoryDenmark
CityArhus
Period28/08/0131/08/01
Internet address

Cite this