Top

Published in:

2020 | OriginalPaper | Chapter

Planar Projections of Graphs

Authors : N. R. Aravind, Udit Maniyar

Published in: Algorithms and Discrete Applied Mathematics

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We introduce and study a new graph representation where vertices are embedded in three or more dimensions, and in which the edges are drawn on the projections onto the axis-parallel planes. We show that the complete graph on n vertices has a representation in \(\lceil \sqrt{n/2}+1 \rceil \) planes. In 3 dimensions, we show that there exist graphs with \(6n-15\) edges that can be projected onto two orthogonal planes, and that this is best possible. Finally, we obtain bounds in terms of parameters such as geometric thickness and linear arboricity. Using such a bound, we show that every graph of maximum degree 5 has a plane-projectable representation in 3 dimensions.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

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

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

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

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

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

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

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

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Minimum Conflict Free Colouring Parameterized by Treewidth

next chapter New Algorithms and Bounds for Halving Pseudolines

Alon, N.: The linear arboricity of graphs. Isr. J. Math. 62(3), 311–325 (1988)MathSciNetMATHCrossRef

Barát, J., Matoušek, J., Wood, D.R.: Bounded-degree graphs have arbitrarily large geometric thickness. Electron. J. Comb. 13(1), 3 (2006)MathSciNetMATH

Bläsius, T., Kobourov, S.G., Rutter, I.: Simultaneous embedding of planar graphs. In: Handbook on Graph Drawing and Visualization, pp. 349–381. Chapman and Hall/CRC (2013)

Dillencourt, M.B., Eppstein, D., Hirschberg, D.S.: Geometric thickness of complete graphs. J. Graph Algorithms Appl. 4(3), 5–17 (2000)MathSciNetMATHCrossRef

Dujmovic, V., Wood, D.R.: On linear layouts of graphs. Discrete Math. Theor. Comput. Sci. 6(2), 339–358 (2004)MathSciNetMATH

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

Duncan, C.A.: On graph thickness, geometric thickness, and separator theorems. Comput. Geom. 44(2), 95–99 (2011)MathSciNetMATHCrossRef

Duncan, C.A., Eppstein, D., Kobourov, S.G.: The geometric thickness of low degree graphs. In: Proceedings of the 20th ACM Symposium on Computational Geometry, Brooklyn, New York, USA, 8–11 June 2004, pp. 340–346 (2004)

Durocher, S., Gethner, E., Mondal, D.: Thickness and colorability of geometric graphs. Comput. Geom. 56, 1–18 (2016)MathSciNetMATHCrossRef

10.

Enomoto, H., Péroche, B.: The linear arboricity of some regular graphs. J. Graph Theory 8(2), 309–324 (1984)MathSciNetMATHCrossRef

11.

Estrella-Balderrama, A., Fowler, J.J., Kobourov, S.G.: Characterization of unlabeled level planar trees. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol. 4372, pp. 367–379. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-70904-6_35CrossRef

12.

Gonçalves, D., Ochem, P.: On star and caterpillar arboricity. Discrete Math. 309(11), 3694–3702 (2009)MathSciNetMATHCrossRef

13.

Halton, J.H.: On the thickness of graphs of given degree. Inf. Sci. 54(3), 219–238 (1991)MathSciNetMATHCrossRef

14.

Hutchinson, J.P., Shermer, T.C., Vince, A.: On representations of some thickness-two graphs. Comput. Geom. 13(3), 161–171 (1999)MathSciNetMATHCrossRef

15.

Malviya, P.: Graph visualization. Master’s thesis, Indian Institute of Technology Hyderabad (2016)

16.

Mutzel, P., Odenthal, T., Scharbrodt, M.: The thickness of graphs: a survey. Graphs Comb. 14(1), 59–73 (1998)MathSciNetMATHCrossRef

17.

Ollmann, T.: On the book thickness of various graphs. In: Proceedings of the 4th SouthEastern Conference on Combinatorics, Graph Theory and Computing, vol. VIII, p. 459 (1973)

18.

Tutte, W.: The thickness of a graph. Indag. Math. 25, 567–577 (1963)MathSciNetMATHCrossRef

Title: Planar Projections of Graphs
Authors: N. R. Aravind
Udit Maniyar
Publisher: Springer International Publishing
Book: Algorithms and Discrete Applied Mathematics
Print ISBN: 978-3-030-39218-5

Electronic ISBN: 978-3-030-39219-2

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-39219-2_36

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner