Top

previous chapter Simultaneous Orthogonal Planarity

next chapter Evaluation of Two Interaction Techniques for Vi...

Hint

Swipe to navigate through the chapters of this book

2016 | OriginalPaper | Chapter

Monotone Simultaneous Embeddings of Paths in d Dimensions

Authors: David Bremner, Olivier Devillers, Marc Glisse, Sylvain Lazard, Giuseppe Liotta, Tamara Mchedlidze, Sue Whitesides, Stephen Wismath

Publisher: Springer International Publishing

Published in: Graph Drawing and Network Visualization

» Get access to the full-text

Abstract

We study the following problem: Given k paths that share the same vertex set, is there a simultaneous geometric embedding of these paths such that each individual drawing is monotone in some direction? We prove that, for any dimension d, there is a set of \(d+1\) paths that does not admit a monotone simultaneous geometric embedding.

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

We reference the reader to [ 8] for the full version of this paper.

Aichholzer, O., Hackl, T., Lutteropp, S., Mchedlidze, T., Pilz, A., Vogtenhuber, B.: Monotone simultaneous embeddings of upward planar digraphs. J. Graph Algorithms Appl. 19(1), 87–110 (2015) MathSciNetCrossRefMATH

Angelini, P., Colasante, E., Battista, G.D., Frati, F., Patrignani, M.: Monotone drawings of graphs. J. Graph Algorithms Appl. 16(1), 5–35 (2012) MathSciNetCrossRefMATH

Angelini, P., Didimo, W., Kobourov, S.G., Mchedlidze, T., Roselli, V., Symvonis, A., Wismath, S.K.: Monotone drawings of graphs with fixed embedding. Algorithmica 71(2), 233–257 (2015) MathSciNetCrossRefMATH

Angelini, P., Geyer, M., Kaufmann, M., Neuwirth, D.: On a tree and a path with no geometric simultaneous embedding. J. Graph Algorithms Appl. 16(1), 37–83 (2012) MathSciNetCrossRefMATH

Asinowski, A.: Suballowable sequences and geometric permutations. Discret. Math. 308(20), 4745–4762 (2008) MathSciNetCrossRefMATH

Blaäsius, T., Kobourov, S.G., Rutter, I.: Simultaneous embedding of planar graphs. In: Tamassia, R. (ed.) Handbook on Graph Drawing and Visualization. Chapman and Hall/CRC, Boca Raton (2013)

Braß, P., Cenek, E., Duncan, C.A., Efrat, A., Erten, C., Ismailescu, D.P., Kobourov, S.G., Lubiw, A., Mitchell, J.S.B.: On simultaneous planar graph embeddings. Comput. Geom. 36(2), 117–130 (2007) MathSciNetCrossRefMATH

Bremner, D., Devillers, O., Glisse, M., Lazard, S., Liotta, G., Mchedlidze, T., Whitesides, S., Wismath, S.: Monotone simultaneous embeddings of paths in \(\mathbb{R}^d\) (2016). http://arxiv.org/abs/1608.08791

Erten, C., Kobourov, S.G.: Simultaneous embedding of planar graphs with few bends. J. Graph Algorithms Appl. 9(3), 347–364 (2005) MathSciNetCrossRefMATH

10.

Felsner, S., Igamberdiev, A., Kindermann, P., Klemz, B., Mchedlidze, T., Scheucher, M.: Strongly monotone drawings of planar graphs. In: Fekete, S., Lubiw, A. (eds.) 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), vol. 51, pp. 37:1–37:15. Dagstuhl, Germany (2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik

11.

Giacomo, E.D., Didimo, W., Liotta, G., Meijer, H., Wismath, S.K.: Planar and quasi-planar simultaneous geometric embedding. Comput. J. 58(11), 3126–3140 (2015) CrossRefMATH

12.

Hossain, M.I., Rahman, M.S.: Straight-line monotone grid drawings of series-parallel graphs. Discret. Math. Algorithms Appl. 7(2), 1550007-1–1550007-12 (2015) MathSciNetMATH

13.

Kindermann, P., Schulz, A., Spoerhase, J., Wolff, A.: On monotone drawings of trees. In: Duncan, C., Symvonis, A. (eds.) GD 2014. LNCS, vol. 8871, pp. 488–500. Springer, Heidelberg (2014). doi: 10.1007/978-3-662-45803-7_41

Title

Monotone Simultaneous Embeddings of Paths in d Dimensions

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_42

Authors:

David Bremner
Olivier Devillers
Marc Glisse
Sylvain Lazard
Giuseppe Liotta
Tamara Mchedlidze
Sue Whitesides
Stephen Wismath

Publisher

Springer International Publishing

Sequence number

Premium Partner

Image Credits