Track layout is hard

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

doi:10.1007/978-3-319-50106-2_38

Track layout is hard

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

School of Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

3 Citations (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 language	English
Title of host publication	Graph Drawing and Network Visualization
Subtitle of host publication	24th International Symposium, GD 2016 Athens, Greece, September 19-21 2016, Revised Selected Papers
Editors	Yifan Hu, Martin Nöllenburg
Place of Publication	Cham Switzerland
Publisher	Springer
Pages	499-510
Number of pages	12
ISBN (Electronic)	9783319501062
ISBN (Print)	9783319501055
DOIs	https://doi.org/10.1007/978-3-319-50106-2_38
Publication status	Published - 2016
Event	Graph Drawing 2016 - Ionic Centre, Athens, Greece Duration: 19 Sep 2016 → 21 Sep 2016 Conference number: 24 http://algo.math.ntua.gr/~gd2016/ https://link.springer.com/book/10.1007/978-3-319-50106-2 (Proceedings)

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	9801
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	Graph Drawing 2016
Abbreviated title	GD 2016
Country/Territory	Greece
City	Athens
Period	19/09/16 → 21/09/16
Other	The 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	http://algo.math.ntua.gr/~gd2016/ https://link.springer.com/book/10.1007/978-3-319-50106-2 (Proceedings)

Access to Document

10.1007/978-3-319-50106-2_38

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 ). Springer. https://doi.org/10.1007/978-3-319-50106-2_38

@inproceedings{a3de84b3de1c4339a70b552640565df7,

title = "Track layout is hard",

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.",

author = "Bannister, {Michael J.} and Devanny, {William E.} and Vida Dujmovic and David Eppstein and Wood, {David R.}",

year = "2016",

doi = "10.1007/978-3-319-50106-2_38",

language = "English",

isbn = "9783319501055",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "499--510",

editor = "Hu, {Yifan } and N{\"o}llenburg, {Martin }",

booktitle = "Graph Drawing and Network Visualization",

note = "Graph Drawing 2016, GD 2016 ; Conference date: 19-09-2016 Through 21-09-2016",

url = "http://algo.math.ntua.gr/~gd2016/, https://link.springer.com/book/10.1007/978-3-319-50106-2",

}

Bannister, MJ, Devanny, WE, Dujmovic, V, Eppstein, D & Wood, DR 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. Lecture Notes in Computer Science, vol. 9801 , Springer, Cham Switzerland, pp. 499-510, Graph Drawing 2016, Athens, Greece, 19/09/16. https://doi.org/10.1007/978-3-319-50106-2_38

Track layout is hard. / Bannister, Michael J.; Devanny, William E.; Dujmovic, Vida et al.

Graph Drawing and Network Visualization: 24th International Symposium, GD 2016 Athens, Greece, September 19-21 2016, Revised Selected Papers. ed. / Yifan Hu; Martin Nöllenburg. Cham Switzerland : Springer, 2016. p. 499-510 (Lecture Notes in Computer Science; Vol. 9801 ).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - Track layout is hard

AU - Bannister, Michael J.

AU - Devanny, William E.

AU - Dujmovic, Vida

AU - Eppstein, David

AU - Wood, David R.

N1 - Conference code: 24

PY - 2016

Y1 - 2016

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85007348876&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-50106-2_38

DO - 10.1007/978-3-319-50106-2_38

M3 - Conference Paper

AN - SCOPUS:85007348876

SN - 9783319501055

T3 - Lecture Notes in Computer Science

SP - 499

EP - 510

BT - Graph Drawing and Network Visualization

A2 - Hu, Yifan

A2 - Nöllenburg, Martin

PB - Springer

CY - Cham Switzerland

T2 - Graph Drawing 2016

Y2 - 19 September 2016 through 21 September 2016

ER -

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

Track layout is hard

Abstract

Publication series

Conference

Access to Document

Other files and links

Graph colouring via entropy compression

Cite this

Track layout is hard

Abstract

Publication series

Conference

Access to Document

Other files and links

Projects

Graph colouring via entropy compression

Cite this