Top

Published in:

2015 | OriginalPaper | Chapter

Pixel and Voxel Representations of Graphs

Authors : Md. Jawaherul Alam, Thomas Bläsius, Ignaz Rutter, Torsten Ueckerdt, 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

AI-assisted search

Off

Abstract

We study contact representations for graphs, which we call pixel representations in 2D and voxel representations in 3D. Our representations are based on the unit square grid whose cells we call pixels in 2D and voxels in 3D. Two pixels are adjacent if they share an edge, two voxels if they share a face. We call a connected set of pixels or voxels a blob. Given a graph, we represent its vertices by disjoint blobs such that two blobs contain adjacent pixels or voxels if and only if the corresponding vertices are adjacent. We are interested in the size of a representation, which is the number of pixels or voxels it consists of.

We first show that finding minimum-size representations is NP-complete. Then, we bound representation sizes needed for certain graph classes. In 2D, we show that, for k-outerplanar graphs with n vertices, \(\varTheta (kn)\) pixels are always sufficient and sometimes necessary. In particular, outerplanar graphs can be represented with a linear number of pixels, whereas general planar graphs sometimes need a quadratic number. In 3D, \(\varTheta (n^2)\) voxels are always sufficient and sometimes necessary for any n-vertex graph. We improve this bound to \(\varTheta (n\cdot \tau )\) for graphs of treewidth \(\tau \) and to \(O((g+1)^2n\log ^2n)\) for graphs of genus g. In particular, planar graphs admit representations with \(O(n\log ^2n)\) voxels.

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 Towards Characterizing Graphs with a Sliceable Rectangular Dual

next chapter A Tale of Two Communities: Assessing Homophily in Node-Link Diagrams

Aerts, N., Felsner, S.: Vertex contact graphs of paths on a grid. In: Kratsch, D., Todinca, I. (eds.) WG 2014. LNCS, vol. 8747, pp. 56–68. Springer, Heidelberg (2014)

Alam, M.J., Biedl, T., Felsner, S., Kaufmann, M., Kobourov, S., Ueckerdt, T.: Computing cartograms with optimal complexity. Discrete Comput. Geom. 50(3), 784–810 (2013)MathSciNetCrossRefMATH

Alam, M.J., Bläsius, T., Rutter, I., Ueckerdt, T., Wolff, A.: Pixel and voxel representations of graphs. Arxiv report (2015). arxiv.org/abs/1507.01450

Badent, M., Binucci, C., Di Giacomo, E., Didimo, W., Felsner, S., Giordano, F., Kratochvíl, J., Palladino, P., Patrignani, M., Trotta, F.: Homothetic triangle contact representations of planar graphs. In: Canadian Conference on Computational Geometry (CCCG 2007), pp. 233–236 (2007)

Bezdek, A.: On the number of mutually touching cylinders. Comb. Comput. Geom. 52, 121–127 (2005)MathSciNet

Bezdek, K., Reid, S.: Contact graphs of unit sphere packings revisited. J. Geom. 104(1), 57–83 (2013)MathSciNetCrossRefMATH

Bhatt, S.N., Cosmadakis, S.S.: The complexity of minimizing wire lengths in VLSI layouts. Inform. Process. Lett. 25(4), 263–267 (1987)CrossRefMATH

Biedl, T.: On triangulating \(k\)-outerplanar graphs. Discrete Appl. Math. 181, 275–279 (2015). arxiv.org/abs/1310.1845 MathSciNetCrossRefMATH

Biedl, T.C.: Small drawings of outerplanar graphs, series-parallel graphs, and other planar graphs. Discrete Comput. Geom. 45(1), 141–160 (2011)MathSciNetCrossRefMATH

10.

Bodlaender, H.L.: Treewidth: algorithmic techniques and results. In: Prívara, I., Ružička, P. (eds.) MFCS 1997. LNCS, vol. 1295, pp. 19–36. Springer, Heidelberg (1997) CrossRef

11.

Bose, P., Everett, H., Fekete, S.P., Houle, M.E., Lubiw, A., Meijer, H., Romanik, K., Rote, G., Shermer, T.C., Whitesides, S., Zelle, C.: A visibility representation for graphs in three dimensions. J. Graph Algorithms Appl. 2(3), 1–16 (1998)MathSciNetCrossRef

12.

Brandenburg, F.J., Eppstein, D., Goodrich, M.T., Kobourov, S.G., Liotta, G., Mutzel, P.: Selected open problems in graph drawing. In: Liotta, G. (ed.) GD 2003. LNCS, vol. 2912, pp. 515–539. Springer, Heidelberg (2004) CrossRef

13.

Brandenburg, F.J.: 1-visibility representations of 1-planar graphs. J. Graph Algorithms Appl. 18(3), 421–438 (2014)MathSciNetCrossRefMATH

14.

Bremner, D., et al.: On representing graphs by touching cuboids. In: Didimo, W., Patrignani, M. (eds.) GD 2012. LNCS, vol. 7704, pp. 187–198. Springer, Heidelberg (2013) CrossRef

15.

Buchsbaum, A.L., Gansner, E.R., Procopiuc, C.M., Venkatasubramanian, S.: Rectangular layouts and contact graphs. ACM Trans. Algorithms 4(1), 8–28 (2008)MathSciNetCrossRef

16.

Cano, R., Buchin, K., Castermans, T., Pieterse, A., Sonke, W., Speckmann, B.: Mosaic drawings and cartograms. Comput. Graph. Forum 34(3), 361–370 (2015)CrossRef

17.

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(2), 153–162 (2002)MathSciNetCrossRefMATH

18.

Chaplick, S., Kobourov, S.G., Ueckerdt, T.: Equilateral L-contact graphs. In: Brandstädt, A., Jansen, K., Reischuk, R. (eds.) WG 2013. LNCS, vol. 8165, pp. 139–151. Springer, Heidelberg (2013) CrossRef

19.

Di Battista, G., Frati, F.: Small area drawings of outerplanar graphs. Algorithmica 54(1), 25–53 (2009)MathSciNetCrossRefMATH

20.

Dolev, D., Leighton, T., Trickey, H.: Planar embedding of planar graphs. Adv. Comput. Res. 2, 147–161 (1984)

21.

Dujmović, V., Morin, P., Wood, D.: Layered separators for queue layouts, 3d graph drawing and nonrepetitive coloring. In: Foundations of Computer Science (FOCS 2013), pp. 280–289. IEEE (2013)

22.

Duncan, C.A., Gansner, E.R., Hu, Y.F., Kaufmann, M., Kobourov, S.G.: Optimal polygonal representation of planar graphs. Algorithmica 63(3), 672–691 (2012)MathSciNetCrossRefMATH

23.

Evans, W., Kaufmann, M., Lenhart, W., Mchedlidze, T., Wismath, S.: Bar 1-visibility graphs and their relation to other nearly planar graphs. J. Graph Algorithms Appl. 18(5), 721–739 (2014)MathSciNetCrossRefMATH

24.

Fan, J.-H., Lin, C.-C., Lu, H.-I., Yen, H.-C.: Width-optimal visibility representations of plane graphs. In: Tokuyama, T. (ed.) ISAAC 2007. LNCS, vol. 4835, pp. 160–171. Springer, Heidelberg (2007) CrossRef

25.

Felsner, S.: Rectangle and square representations of planar graphs. Thirty Essays on Geometric Graph Theory, pp. 213–248 (2013)

26.

Felsner, S., Francis, M.C.: Contact representations of planar graphs with cubes. In: Symposium on Computational Geometry (SoCG 2011), pp. 315–320. ACM (2011)

27.

Fomin, F.V., Thilikos, D.M.: New upper bounds on the decomposability of planar graphs. J. Graph Theory 51(1), 53–81 (2006)MathSciNetCrossRef

28.

de Fraysseix, H., de Mendez, P.O.: Representations by contact and intersection of segments. Algorithmica 47(4), 453–463 (2007)MathSciNetCrossRefMATH

29.

de Fraysseix, H., de Mendez, P.O., Rosenstiehl, P.: On triangle contact graphs. Comb. Prob. Comput. 3, 233–246 (1994)CrossRefMATH

30.

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

31.

Hliněný, P., Kratochvíl, J.: Representing graphs by disks and balls (a survey of recognition-complexity results). Discrete Math. 229(1–3), 101–124 (2001)MathSciNetCrossRefMATH

32.

Koebe, P.: Kontaktprobleme der konformen Abbildung. Berichte über die Verhandlungen der Sächsischen Akademie der Wissenschaften zu Leipzig. Math. Phy. Kla. 88, 141–164 (1936)

33.

Leiserson, C.E.: Area-efficient graph layouts (for VLSI). In: Foundations of Computer Science (FOCS 1980), pp. 270–281. IEEE (1980)

34.

Pach, J., Thiele, T., Tóth, G.: Three-dimensional grid drawings of graphs. In: Di Battista, G. (ed.) GD 1997. LNCS, vol. 1353, pp. 47–51. Springer, Heidelberg (1997) CrossRef

35.

Patrignani, M.: Complexity results for three-dimensional orthogonal graph drawing. J. Discrete Algorithms 6(1), 140–161 (2008)MathSciNetCrossRefMATH

36.

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

37.

Tamassia, R., Tollis, I.G.: A unified approach a visibility representation of planar graphs. Discrete Comput. Geom. 1, 321–341 (1986)MathSciNetCrossRefMATH

38.

Thomassen, C.: Interval representations of planar graphs. J. Comb. Theory B 40(1), 9–20 (1986)MathSciNetCrossRefMATH

39.

Zong, C.: The kissing numbers of tetrahedra. Discrete Comput. Geom. 15(3), 239–252 (1996)MathSciNetCrossRefMATH

Title: Pixel and Voxel Representations of Graphs
Authors: Md. Jawaherul Alam
Thomas Bläsius
Ignaz Rutter
Torsten Ueckerdt
Alexander Wolff
Publisher: Springer International Publishing
Book: Graph Drawing and Network Visualization
Print ISBN: 978-3-319-27260-3

Electronic ISBN: 978-3-319-27261-0

Copyright Year: 2015
DOI: https://doi.org/10.1007/978-3-319-27261-0_39

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