nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

Drawing Graphs on Few Lines and Few Planes

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

Erschienen in: Graph Drawing and Network Visualization

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

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.

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel Drawing Planar Graphs with Many Collinear Vertices

Nächstes Kapitel Algorithms for Visualizing Phylogenetic Networks

A triangulation G with \({{\mathrm{segm}}}(G)=O(\sqrt{n})\) has been found by Dujmović et al. [14, Fig. 12].

Akiyama, J., Era, H., Gervacio, S.V., Watanabe, M.: Path chromatic numbers of graphs. J. Graph Theory 13(5), 571–573 (1989)MathSciNetCrossRefMATH

Akiyama, J., Exoo, G., Harary, F.: Covering and packing ingraphs III: cyclic and acyclic invariants. Math. Slovaca 30, 405–417 (1980)MathSciNetMATH

Bannister, M.J., Devanny, W.E., Dujmović, V., Eppstein, D., Wood, D.R.: Track layouts, layered path decompositions, and leveled planarity (2015). http://arxiv.org/abs/1506.09145

Battista, G.D., Frati, F., Pach, J.: On the queue number of planar graphs. SIAM J. Comput. 42(6), 2243–2285 (2013)MathSciNetCrossRefMATH

Bollobás, B.: Combinatorics: Set Systems, Hypergraphs, Families of Vectors and Combinatorial Probability, 1st edn. Cambridge University Press, Cambridge (1986)MATH

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)

Brooks, R.L.: On colouring the nodes of a network. Math. Proc. Camb. Philos. Soc. 37, 194–197 (1941)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

Chaplick, S., Fleszar, K., Lipp, F., Ravsky, A., Verbitsky, O., Wolff, A.: The complexity of drawing graphs on few lines and few planes (2016). http://arxiv.org/abs/1607.06444

10.

Chaplick, S., Fleszar, K., Lipp, F., Ravsky, A., Verbitsky, O., Wolff, A.: Drawing graphs on few lines and few planes (2016). http://arxiv.org/abs/1607.01196

11.

Chartrand, G., Kronk, H.V.: The point-arboricity of planar graphs. J. Lond. Math. Soc. 44, 612–616 (1969)MathSciNetCrossRefMATH

12.

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

13.

Dujmović, V.: Graph layouts via layered separators. J. Comb. Theory Ser. B 110, 79–89 (2015)MathSciNetCrossRefMATH

14.

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.

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

16.

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)

17.

Durocher, S., Mondal, D.: Drawing plane triangulations with few segments. In: Proceedings of the Canadian Conference Computational Geometry (CCCG 2014), pp. 40–45 (2014). http://cccg.ca/proceedings/2014/papers/paper06.pdf

18.

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.

Flum, J., Grohe, M.: Parametrized Complexity Theory. Springer, Berlin (2006)MATH

20.

de Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica 10(1), 41–51 (1990)MathSciNetCrossRefMATH

21.

Goddard, W.: Acyclic colorings of planar graphs. Discrete Math. 91(1), 91–94 (1991)MathSciNetCrossRefMATH

22.

Grünbaum, B., Walther, H.: Shortness exponents of families of graphs. J. Comb. Theory Ser. A 14(3), 364–385 (1973)MathSciNetCrossRefMATH

23.

Hanani, H.: The existence and construction of balanced incomplete block designs. Ann. Math. Stat. 32, 361–386 (1961). http://www.jstor.org/stable/2237750 MathSciNetCrossRefMATH

24.

Harary, F.: Covering and packing in graphs I. Ann. N.Y. Acad. Sci. 175, 198–205 (1970)MathSciNetCrossRefMATH

25.

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.

Krein, M., Milman, D.: On extreme points of regular convex sets. Studia Math. 9, 133–138 (1940)MathSciNetMATH

27.

Matsumoto, M.: Bounds for the vertex linear arboricity. J. Graph Theory 14(1), 117–126 (1990)MathSciNetCrossRefMATH

28.

Pach, J., Thiele, T., Tóth, G.: Three-dimensional grid drawings of graphs. In: DiBattista, G. (ed.) GD 1997. LNCS, vol. 1353, pp. 47–51. Springer, Heidelberg (1997). doi:10.1007/3-540-63938-1_49 CrossRef

29.

Poh, K.S.: On the linear vertex-arboricity of a planar graph. J. Graph Theory 14(1), 73–75 (1990)MathSciNetCrossRefMATH

30.

Raspaud, A., Wang, W.: On the vertex-arboricity of planar graphs. Eur. J. Comb. 29(4), 1064–1075 (2008)MathSciNetCrossRefMATH

31.

Ravsky, A., Verbitsky, O.: On collinear sets in straight-line drawings. In: Kolman, P., Kratochvíl, J. (eds.) WG 2011. LNCS, vol. 6986, pp. 295–306. Springer, Heidelberg (2011). doi:10.1007/978-3-642-25870-1_27. https://arXiv.org/abs/0806.0253 CrossRef

32.

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.

Schnyder, W.: Embedding planar graphs on the grid. In: Proceedings of the 1st ACM-SIAM Symposium Discrete Algorithms (SODA 1990), pp. 138–148 (1990)

34.

Schulz, A.: Drawing graphs with few arcs. J. Graph Algorithms Appl. 19(1), 393–412 (2015)MathSciNetCrossRefMATH

35.

Wang, J.: On point-linear arboricity of planar graphs. Discrete Math. 72(1–3), 381–384 (1988)MathSciNetCrossRefMATH

36.

Wikipedia: Krein-Milman theorem. https://en.wikipedia.org/wiki/Krein-Milman_theorem. Accessed 21 Apr 2016

37.

Wood, D.R.: Three-dimensional graph drawing. In: Kao, M.Y. (ed.) Encyclopedia of Algorithms, pp. 1–7. Springer, Boston (2008)

Titel: Drawing Graphs on Few Lines and Few Planes
verfasst von: Steven Chaplick
Krzysztof Fleszar
Fabian Lipp
Alexander Ravsky
Oleg Verbitsky
Alexander Wolff
Verlag: Springer International Publishing
Buch: Graph Drawing and Network Visualization
Print ISBN: 978-3-319-50105-5

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

Copyright-Jahr: 2016
DOI: https://doi.org/10.1007/978-3-319-50106-2_14

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"