Skip to main content
Top

2016 | OriginalPaper | Chapter

Drawing Graphs on Few Lines and Few Planes

Authors : Steven Chaplick, Krzysztof Fleszar, Fabian Lipp, Alexander Ravsky, Oleg Verbitsky, Alexander Wolff

Published in: Graph Drawing and Network Visualization

Publisher: Springer International Publishing

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

search-config
loading …

Abstract

We investigate the problem of drawing graphs in 2D and 3D such that their edges (or only their vertices) can be covered by few lines or planes. We insist on straight-line edges and crossing-free drawings. This problem has many connections to other challenging graph-drawing problems such as small-area or small-volume drawings, layered or track drawings, and drawing graphs with low visual complexity. While some facts about our problem are implicit in previous work, this is the first treatment of the problem in its full generality. Our contribution is as follows.
  • We show lower and upper bounds for the numbers of lines and planes needed for covering drawings of graphs in certain graph classes. In some cases our bounds are asymptotically tight; in some cases we are able to determine exact values.
  • We relate our parameters to standard combinatorial characteristics of graphs (such as the chromatic number, treewidth, maximum degree, or arboricity) and to parameters that have been studied in graph drawing (such as the track number or the number of segments appearing in a drawing).
  • We pay special attention to planar graphs. For example, we show that there are planar graphs that can be drawn in 3-space on a lot fewer lines than in the plane.

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!

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!

Footnotes
1
A triangulation G with \({{\mathrm{segm}}}(G)=O(\sqrt{n})\) has been found by Dujmović et al. [14, Fig. 12].
 
Literature
1.
2.
go back to reference Akiyama, J., Exoo, G., Harary, F.: Covering and packing ingraphs III: cyclic and acyclic invariants. Math. Slovaca 30, 405–417 (1980)MathSciNetMATH Akiyama, J., Exoo, G., Harary, F.: Covering and packing ingraphs III: cyclic and acyclic invariants. Math. Slovaca 30, 405–417 (1980)MathSciNetMATH
5.
go back to reference Bollobás, B.: Combinatorics: Set Systems, Hypergraphs, Families of Vectors and Combinatorial Probability, 1st edn. Cambridge University Press, Cambridge (1986)MATH Bollobás, B.: Combinatorics: Set Systems, Hypergraphs, Families of Vectors and Combinatorial Probability, 1st edn. Cambridge University Press, Cambridge (1986)MATH
6.
go back to reference Broere, I., Mynhardt, C.M.: Generalized colorings of outerplanar and planar graphs. In: Proceedings of the 5th International Conference Graph Theory Applications Algorithms and Computer Science, Kalamazoo, MI, pp. 151–161 (1984, 1985) Broere, I., Mynhardt, C.M.: Generalized colorings of outerplanar and planar graphs. In: Proceedings of the 5th International Conference Graph Theory Applications Algorithms and Computer Science, Kalamazoo, MI, pp. 151–161 (1984, 1985)
8.
go back to reference Chan, T.M., Goodrich, M.T., Kosaraju, S.R., Tamassia, R.: Optimizing area and aspect ratio in straight-line orthogonal tree drawings. Comput. Geom. Theory Appl. 23, 153–162 (2002)MathSciNetCrossRefMATH Chan, T.M., Goodrich, M.T., Kosaraju, S.R., Tamassia, R.: Optimizing area and aspect ratio in straight-line orthogonal tree drawings. Comput. Geom. Theory Appl. 23, 153–162 (2002)MathSciNetCrossRefMATH
12.
go back to reference Chen, Z., He, X.: Parallel complexity of partitioning a planar graph into vertex-induced forests. Discrete Appl. Math. 69(1–2), 183–198 (1996)MathSciNetMATH Chen, Z., He, X.: Parallel complexity of partitioning a planar graph into vertex-induced forests. Discrete Appl. Math. 69(1–2), 183–198 (1996)MathSciNetMATH
14.
go back to reference Dujmović, V., Eppstein, D., Suderman, M., Wood, D.R.: Drawings of planar graphs with few slopes and segments. Comput. Geom. Theory Appl. 38(3), 194–212 (2007)MathSciNetCrossRefMATH Dujmović, V., Eppstein, D., Suderman, M., Wood, D.R.: Drawings of planar graphs with few slopes and segments. Comput. Geom. Theory Appl. 38(3), 194–212 (2007)MathSciNetCrossRefMATH
15.
16.
go back to reference Dujmović, V., Whitesides, S.: Three-dimensional drawings. In: Tamassia, R. (ed.) Handbook of Graph Drawing and Visualization, chap. 14, pp. 455–488. CRC Press, Boca Raton (2013) Dujmović, V., Whitesides, S.: Three-dimensional drawings. In: Tamassia, R. (ed.) Handbook of Graph Drawing and Visualization, chap. 14, pp. 455–488. CRC Press, Boca Raton (2013)
18.
go back to reference Felsner, S., Liotta, G., Wismath, S.: Straight-line drawings on restricted integer grids in two and three dimensions. J. Graph Algorithms Appl. 7(4), 363–398 (2003)MathSciNetCrossRefMATH Felsner, S., Liotta, G., Wismath, S.: Straight-line drawings on restricted integer grids in two and three dimensions. J. Graph Algorithms Appl. 7(4), 363–398 (2003)MathSciNetCrossRefMATH
19.
go back to reference Flum, J., Grohe, M.: Parametrized Complexity Theory. Springer, Berlin (2006)MATH Flum, J., Grohe, M.: Parametrized Complexity Theory. Springer, Berlin (2006)MATH
25.
go back to reference Kostochka, A., Melnikov, L.: On a lower bound for the isoperimetric number of cubic graphs. In: Proceedings of the 3rd International Petrozavodsk Conference Probabilistic Methods in Discrete Mathematics, pp. 251–265. TVP, Moskva, VSP, Utrecht (1993) Kostochka, A., Melnikov, L.: On a lower bound for the isoperimetric number of cubic graphs. In: Proceedings of the 3rd International Petrozavodsk Conference Probabilistic Methods in Discrete Mathematics, pp. 251–265. TVP, Moskva, VSP, Utrecht (1993)
26.
32.
go back to reference Schaefer, M., Štefankovič, D.: Fixed points, Nash equilibria, and the existential theory of the reals. Theory Comput. Syst., 1–22 (2015, has appeared online) Schaefer, M., Štefankovič, D.: Fixed points, Nash equilibria, and the existential theory of the reals. Theory Comput. Syst., 1–22 (2015, has appeared online)
33.
go back to reference Schnyder, W.: Embedding planar graphs on the grid. In: Proceedings of the 1st ACM-SIAM Symposium Discrete Algorithms (SODA 1990), pp. 138–148 (1990) Schnyder, W.: Embedding planar graphs on the grid. In: Proceedings of the 1st ACM-SIAM Symposium Discrete Algorithms (SODA 1990), pp. 138–148 (1990)
37.
go back to reference Wood, D.R.: Three-dimensional graph drawing. In: Kao, M.Y. (ed.) Encyclopedia of Algorithms, pp. 1–7. Springer, Boston (2008) Wood, D.R.: Three-dimensional graph drawing. In: Kao, M.Y. (ed.) Encyclopedia of Algorithms, pp. 1–7. Springer, Boston (2008)
Metadata
Title
Drawing Graphs on Few Lines and Few Planes
Authors
Steven Chaplick
Krzysztof Fleszar
Fabian Lipp
Alexander Ravsky
Oleg Verbitsky
Alexander Wolff
Copyright Year
2016
DOI
https://doi.org/10.1007/978-3-319-50106-2_14

Premium Partner