Track layout is hard

Michael J. Bannister, William E. Devanny, Vida Dujmovic, David Eppstein, David R. Wood

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

1 Citation (Scopus)

Abstract

We show that testing whether a given graph has a 3-track layout is hard, by characterizing the bipartite 3-track graphs in terms of leveled planarity. Additionally, we investigate the parameterized complexity of track layouts, showing that past methods used for book layouts do not work to parameterize the problem by treewidth or almosttree number but that the problem is (non-uniformly) fixed-parameter tractable for tree-depth. We also provide several natural classes of bipartite planar graphs, including the bipartite outerplanar graphs, squaregraphs, and dual graphs of arrangements of monotone curves, that always have 3-track layouts.

Original languageEnglish
Title of host publicationGraph Drawing and Network Visualization
Subtitle of host publication24th International Symposium, GD 2016 Athens, Greece, September 19-21 2016, Revised Selected Papers
EditorsYifan Hu, Martin Nöllenburg
Place of PublicationCham Switzerland
PublisherSpringer
Pages499-510
Number of pages12
ISBN (Electronic)9783319501062
ISBN (Print)9783319501055
DOIs
Publication statusPublished - 2016
EventGraph Drawing 2016 - Ionic Centre, Athens, Greece
Duration: 19 Sep 201621 Sep 2016
Conference number: 24
http://algo.math.ntua.gr/~gd2016/

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume9801
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceGraph Drawing 2016
Abbreviated titleGD 2016
CountryGreece
CityAthens
Period19/09/1621/09/16
OtherThe 24th International Symposium on Graph Drawing & Network Visualization has been the main annual event in this area for more than 20 years. Its focus is on combinatorial and algorithmic aspects of graph drawing as well as the design of network visualization systems and interfaces. GD 2016 will be hosted by the Institute of Communications and Computer Systems, an affiliate of the National Technical University of Athens from September 19 to 21, 2016 in Athens, Greece. Researchers and practitioners working on any aspect of graph drawing and network visualization are invited to contribute papers and posters and to participate in the symposium and the graph drawing contest.
Internet address

Cite this

Bannister, M. J., Devanny, W. E., Dujmovic, V., Eppstein, D., & Wood, D. R. (2016). Track layout is hard. In Y. Hu, & M. Nöllenburg (Eds.), Graph Drawing and Network Visualization: 24th International Symposium, GD 2016 Athens, Greece, September 19-21 2016, Revised Selected Papers (pp. 499-510). (Lecture Notes in Computer Science; Vol. 9801 ). Cham Switzerland: Springer. https://doi.org/10.1007/978-3-319-50106-2_38