Skip to main content

2020 | OriginalPaper | Buchkapitel

Planar Projections of Graphs

verfasst von : N. R. Aravind, Udit Maniyar

Erschienen in: Algorithms and Discrete Applied Mathematics

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

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!

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!

Literatur
2.
Zurück zum Zitat 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 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
3.
Zurück zum Zitat 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) 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)
4.
Zurück zum Zitat Dillencourt, M.B., Eppstein, D., Hirschberg, D.S.: Geometric thickness of complete graphs. J. Graph Algorithms Appl. 4(3), 5–17 (2000)MathSciNetMATHCrossRef Dillencourt, M.B., Eppstein, D., Hirschberg, D.S.: Geometric thickness of complete graphs. J. Graph Algorithms Appl. 4(3), 5–17 (2000)MathSciNetMATHCrossRef
5.
Zurück zum Zitat 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.: On linear layouts of graphs. Discrete Math. Theor. Comput. Sci. 6(2), 339–358 (2004)MathSciNetMATH
6.
Zurück zum Zitat Dujmovic, V., Wood, D.R.: Stacks, queues and tracks: layouts of graph subdivisions. Discrete. Math. Theor. Comput. Sci. 7(1), 155–202 (2005)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
8.
Zurück zum Zitat 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) 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)
9.
14.
Zurück zum Zitat Hutchinson, J.P., Shermer, T.C., Vince, A.: On representations of some thickness-two graphs. Comput. Geom. 13(3), 161–171 (1999)MathSciNetMATHCrossRef Hutchinson, J.P., Shermer, T.C., Vince, A.: On representations of some thickness-two graphs. Comput. Geom. 13(3), 161–171 (1999)MathSciNetMATHCrossRef
15.
Zurück zum Zitat Malviya, P.: Graph visualization. Master’s thesis, Indian Institute of Technology Hyderabad (2016) Malviya, P.: Graph visualization. Master’s thesis, Indian Institute of Technology Hyderabad (2016)
17.
Zurück zum Zitat 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) 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)
Metadaten
Titel
Planar Projections of Graphs
verfasst von
N. R. Aravind
Udit Maniyar
Copyright-Jahr
2020
DOI
https://doi.org/10.1007/978-3-030-39219-2_36