Top

previous chapter Beyond Level Planarity

next chapter Stack and Queue Layouts via Layered Separators

Hint

Swipe to navigate through the chapters of this book

2016 | OriginalPaper | Chapter

Track Layout Is Hard

Read first chapter

Authors: Michael J. Bannister, William E. Devanny, Vida Dujmović, David Eppstein, David R. Wood

Publisher: Springer International Publishing

Published in: Graph Drawing and Network Visualization

» Get access to the full-text

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 almost-tree 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.

Please log in to get access to this content

To get access to this content you need the following product:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 69.000 Bücher
über 500 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Umwelt
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 50.000 Bücher
über 380 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Umwelt
Maschinenbau + Werkstoffe

Testen Sie jetzt 30 Tage kostenlos.

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 58.000 Bücher
über 300 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

inform now

Dujmović, V., Morin, P., Wood, D.R.: Layout of graphs with bounded tree-width. SIAM J. Comput. 34, 553–579 (2005) MathSciNetCrossRefMATH

Dujmović, V., Wood, D.R.: Three-dimensional grid drawings with sub-quadratic volume. In: Pach, J., ed.: Towards a Theory of Geometric Graphs, vol. 342, pp. 55–66. Contemporary Mathematics - American Mathematical Society (2004)

Dujmović, V., Pór, A., Wood, D.R.: Track layouts of graphs. Discrete Math. Theor. Comput. Sci. 6, 497–521 (2004) MathSciNetMATH

Heath, L.S., Rosenberg, A.L.: Laying out graphs using queues. SIAM J. Comput. 21, 927–958 (1992) MathSciNetCrossRefMATH

Bannister, M.J., Eppstein, D.: Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth. In: Duncan, C., Symvonis, A. (eds.) GD 2014. LNCS, vol. 8871, pp. 210–221. Springer, Heidelberg (2014). doi: 10.1007/978-3-662-45803-7_18

Bannister, M.J., Eppstein, D., Simons, J.A.: Fixed parameter tractability of crossing minimization of almost-trees. In: Wismath, S., Wolff, A. (eds.) GD 2013. LNCS, vol. 8242, pp. 340–351. Springer, Heidelberg (2013). doi: 10.1007/978-3-319-03841-4_30 CrossRef

Harary, F., Schwenk, A.: A new crossing number for bipartite graphs. Utilitas Math. 1, 203–209 (1972) MathSciNetMATH

Halin, R.: \(S\)-functions for graphs. J. Geom. 8, 171–186 (1976) MathSciNetCrossRefMATH

Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms 7, 309–322 (1986) MathSciNetCrossRefMATH

10.

Dujmović, V., Morin, P., Wood, D.R.: Layered separators for queue layouts, 3D graph drawing and nonrepetitive coloring. In: Proceedings of 54th Symposium on Foundations of Computer Science (FOCS 2013), pp. 280–289. IEEE Computer Society (2013)

11.

Dujmović, V., Morin, P., Wood, D.R.: Layered separators in minor-closed graph classes with applications. Electronic preprint arXiv:1306.1595 (2013)

12.

Sugiyama, K., Tagawa, S., Toda, M.: Methods for visual understanding of hierarchical system structures. IEEE Trans. Syst. Man Cybern. SMC–11, 109–125 (1981) MathSciNetCrossRef

13.

Eades, P., Wormald, N.C.: Edge crossings in drawings of bipartite graphs. Algorithmica 11, 379–403 (1994) MathSciNetCrossRefMATH

14.

Healy, P., Nikolov, N.S.: How to layer a directed acyclic graph. In: Mutzel, P., Jünger, M., Leipert, S. (eds.) GD 2001. LNCS, vol. 2265, pp. 16–30. Springer, Heidelberg (2002). doi: 10.1007/3-540-45848-4_2 CrossRef

15.

Felsner, S., Liotta, G., Wismath, S.K.: Straight-line drawings on restricted integer grids in two and three dimensions. J. Graph Algorithms Appl. 7, 363–398 (2003) MathSciNetCrossRefMATH

16.

Dujmović, V., Wood, D.R.: Stacks, queues and tracks: layouts of graph subdivisions. Discrete Math. Theor. Comput. Sci. 7, 155–201 (2005) MathSciNetMATH

17.

Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, Berlin (2013) CrossRefMATH

18.

Bannister, M.J., Cabello, S., Eppstein, D.: Parameterized complexity of 1-planarity. In: Dehne, F., Solis-Oba, R., Sack, J.-R. (eds.) WADS 2013. LNCS, vol. 8037, pp. 97–108. Springer, Heidelberg (2013). doi: 10.1007/978-3-642-40104-6_9 CrossRef

19.

Nešetřil, J., de Mendez, P.O.: Sparsity (Graphs, Structures, and Algorithms). Algorithms and Combinatorics, vol. 28. Springer, Heidelberg (2012) MATH

20.

Abel, Z., Demaine, E.D., Demaine, M.L., Eppstein, D., Lubiw, A., Uehara, R.: Flat foldings of plane graphs with prescribed angles and edge lengths. In: Duncan, C., Symvonis, A. (eds.) GD 2014. LNCS, vol. 8871, pp. 272–283. Springer, Heidelberg (2014). doi: 10.1007/978-3-662-45803-7_23

21.

Bandelt, H.J., Chepoi, V., Eppstein, D.: Combinatorics and geometry of finite and infinite squaregraphs. SIAM J. Discrete Math. 24, 1399–1440 (2010) MathSciNetCrossRefMATH

Title

Track Layout Is Hard

Book

Graph Drawing and Network Visualization

Print ISBN: 978-3-319-50105-5

Electronic ISBN: 978-3-319-50106-2

https://doi.org/10.1007/978-3-319-50106-2

DOI

https://doi.org/10.1007/978-3-319-50106-2_38

Authors:

Michael J. Bannister
William E. Devanny
Vida Dujmović
David Eppstein
David R. Wood

Publisher

Springer International Publishing

Sequence number

Premium Partner

Image Credits