Top

previous chapter Low Ply Drawings of Trees

next chapter The Partial Visibility Representation Extension...

Hint

Swipe to navigate through the chapters of this book

2016 | OriginalPaper | Chapter

Visibility Representations of Boxes in 2.5 Dimensions

Authors: Alessio Arleo, Carla Binucci, Emilio Di Giacomo, William S. Evans, Luca Grilli, Giuseppe Liotta, Henk Meijer, Fabrizio Montecchiani, Sue Whitesides, Stephen Wismath

Publisher: Springer International Publishing

Published in: Graph Drawing and Network Visualization

» Get access to the full-text

Abstract

We initiate the study of 2.5D box visibility representations (2.5D-BR) where vertices are mapped to 3D boxes having the bottom face in the plane \(z=0\) and edges are unobstructed lines of sight parallel to the x- or y-axis. We prove that: (i) Every complete bipartite graph admits a 2.5D-BR; (ii) The complete graph \(K_n\) admits a 2.5D-BR if and only if \(n \leqslant 19\); (iii) Every graph with pathwidth at most 7 admits a 2.5D-BR, which can be computed in linear time. We then turn our attention to 2.5D grid box representations (2.5D-GBR) which are 2.5D-BRs such that the bottom face of every box is a unit square at integer coordinates. We show that an n-vertex graph that admits a 2.5D-GBR has at most \(4n - 6 \sqrt{n}\) edges and this bound is tight. Finally, we prove that deciding whether a given graph G admits a 2.5D-GBR with a given footprint is NP-complete. The footprint of a 2.5D-BR \(\varGamma \) is the set of bottom faces of the boxes in \(\varGamma \).

Please log in to get access to this content

To get access to this content you need the following product:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

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

über 69.000 Bücher
über 500 Zeitschriften

aus folgenden Fachgebieten:

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

Testen Sie jetzt 30 Tage kostenlos.

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 50.000 Bücher
über 380 Zeitschriften

aus folgenden Fachgebieten:

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

Testen Sie jetzt 30 Tage kostenlos.

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 58.000 Bücher
über 300 Zeitschriften

aus folgenden Fachgebieten:

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

Testen Sie jetzt 30 Tage kostenlos.

inform now

Ahmed, M.E., Yusuf, A.B., Polin, M.Z.H.: Bar 1-visibility representation of optimal 1-planar graph. Elect. Inf. Comm. Technol. (EICT) 2013, 1–5 (2014)

Akiyama, T., Nishizeki, T., Saito, N.: NP-completeness of the hamiltonian cycle problem for bipartite graphs. J. Inf. Process. 3(2), 73–76 (1980) MathSciNetMATH

Arleo, A., Binucci, C., Di Giacomo, E, Evans, W.S., Grilli, L., Liotta, G., Meijer, H., Montecchiani, F., Whitesides, S., Wismath, S.: Visibility representations of boxes in 2.5 dimensions. CoRR, abs/1608.08899 (2016)

Biedl, T., Liotta, G., Montecchiani, F.: On visibility representations of non-planar graphs. In: Fekete, S., Lubiw, A., (eds.) SoCG 2016, vol. LIPICs, pp. 19:1–19:16. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2016)

Bose, P., Dean, A., Hutchinson, J., Shermer, T.: On rectangle visibility graphs. In: North, S. (ed.) GD 1996. LNCS, vol. 1190, pp. 25–44. Springer, Heidelberg (1997). doi: 10.1007/3-540-62495-3_35 CrossRef

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) MathSciNetCrossRefMATH

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

Bruckdorfer, T., Kaufmann, M., Montecchiani, F.: 1-bend orthogonal partial edge drawing. J. Graph Algorithms Appl. 18(1), 111–131 (2014) MathSciNetCrossRefMATH

Carmi, P., Friedman, E., Katz, M.J.: Spiderman graph: visibility in urban regions. Comput. Geometry 48(3), 251–259 (2015) MathSciNetCrossRefMATH

10.

Dean, A.M., Ellis-Monaghan, J.A., Hamilton, S., Pangborn, G.: Unit rectangle visibility graphs. Electr. J. Comb. 15(1), 1–24 (2008) MathSciNetMATH

11.

Dean, A.M., Evans, W., Gethner, E., Laison, J.D., Safari, M.A., Trotter, W.T.: Bar \(k\)-visibility graphs. J. Graph Algorithms Appl. 11(1), 45–59 (2007) MathSciNetCrossRefMATH

12.

Dean, A.M., Hutchinson, J.P.: Rectangle-visibility representations of bipartite graphs. Discrete Appl. Math. 75(1), 9–25 (1997) MathSciNetCrossRefMATH

13.

Dean, A.M., Hutchinson, J.P.: Rectangle-visibility layouts of unions and products of trees. J. Graph Algorithms Appl. 2(8), 1–21 (1998) MathSciNetCrossRefMATH

14.

Dean, A.M., Veytsel, N.: Unit bar-visibility graphs. Congr. Num. 160, 161–175 (2003) MathSciNetMATH

15.

Di Giacomo, E., Didimo, W., Evans, W.S., Liotta, G., Meijer, H., Montecchiani, F., Wismath, S.K.: Ortho-polygon visibility representations of embedded graphs. In: Nöllenburg, M., Hu, Y. (eds.) GD 2016. LNCS, vol. 9801, pp. 280–294. Springer, Heidelberg (2016)

16.

Duchet, P., Hamidoune, Y., Las, M., Vergnas, H.M.: Representing a planar graph by vertical lines joining different levels. Discrete Math. 46(3), 319–321 (1983) MathSciNetCrossRefMATH

17.

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

18.

Cobos, F.J., Dana, J.C., Hurtado, F., Márquez, A., Mateos, F.: On a visibility representation of graphs. In: Brandenburg, F.J. (ed.) GD 1995. LNCS, vol. 1027, pp. 152–161. Springer, Heidelberg (1996). doi: 10.1007/BFb0021799 CrossRef

19.

Fekete, S.P., Meijer, H.: Rectangle and box visibility graphs in 3D. Int. J. Comput. Geometry Appl. 9(1), 1–28 (1999) MathSciNetCrossRefMATH

20.

Felsner, S., Massow, M.: Parameters of bar \(k\)-visibility graphs. J. Graph Algorithms Appl. 12(1), 5–27 (2008) MathSciNetCrossRefMATH

21.

Garey, M.R., Johnson, D.S., So, H.C.: An application of graph coloring to printed circuit testing. IEEE Trans. Circuits Syst. CAS–23(10), 591–599 (1976) MathSciNetCrossRefMATH

22.

Gupta, A., Nishimura, N., Proskurowski, A., Ragde, P.: Embeddings of \(k\)-connected graphs of pathwidth \(k\). Discrete Appl. Math. 145(2), 242–265 (2005) MathSciNetCrossRefMATH

23.

Hutchinson, J.P., Shermer, T., Vince, A.: On representations of some thickness-two graphs. Comp. Geometry 13(3), 161–171 (1999) MathSciNetCrossRefMATH

24.

Kant, G., Liotta, G., Tamassia, R., Tollis, I.G.: Area requirement of visibility representations of trees. Inf. Process. Lett. 62(2), 81–88 (1997) MathSciNetCrossRefMATH

25.

Kleitman, J.D., Gyárfás, A., Tóth, G.: Convex sets in the plane with three of every four meeting. Combinatorica 21(2), 221–232 (2001) MathSciNetCrossRefMATH

26.

Liotta, G., Montecchiani, F.: L-visibility drawings of IC-planar graphs. Inf. Process. Lett. 116(3), 217–222 (2016) MathSciNetCrossRefMATH

27.

Otten, R.H.J.M., Van Wijk, J.G.: Graph representations in interactive layout design. In: IEEE ISCSS, pp. 91–918. IEEE (1978)

28.

Rosenstiehl, P., Tarjan, R.E.: Rectilinear planar layouts and bipolar orientations of planar graphs. Discrete Comput. Geom. 1, 343–353 (1986) MathSciNetCrossRefMATH

29.

Shermer, T.C.: On rectangle visibility graphs III. external visibility and complexity. In: Canadian Conference on Computational Geometry, pp. 234–239 (1996)

30.

Štola, J.: Unimaximal sequences of pairs in rectangle visibility drawing. In: Tollis, I.G., Patrignani, M. (eds.) GD 2008. LNCS, vol. 5417, pp. 61–66. Springer, Heidelberg (2009). doi: 10.1007/978-3-642-00219-9_7 CrossRef

31.

Streinu, I., Whitesides, S.: Rectangle visibility graphs: characterization, construction, and compaction. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol. 2607, pp. 26–37. Springer, Heidelberg (2003). doi: 10.1007/3-540-36494-3_4 CrossRef

32.

Sultana, S., Rahman, M.S., Roy, A., Tairin, S.: Bar 1-visibility drawings of 1-planar graphs. In: Gupta, P., Zaroliagis, C. (eds.) ICAA 2014. LNCS, pp. 62–76. Springer International Publishing, New York (2014). doi: 10.1007/978-3-319-04126-1_6

33.

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

34.

Tamassia, R., Tollis, I.G.: Representations of graphs on a cylinder. SIAM J. Discrete Math. 4(1), 139–149 (1991) MathSciNetCrossRefMATH

35.

Thomassen, C.: Plane representations of graphs. In: Progress in Graph Theory, pp. 43–69. AP (1984)

36.

Wismath, S.K.: Characterizing bar line-of-sight graphs. In: Proceedings of 1st Symposium on Computational Geometry, pp. 147–152 (1985)

Title

Visibility Representations of Boxes in 2.5 Dimensions

Book

Graph Drawing and Network Visualization

Print ISBN: 978-3-319-50105-5

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

https://doi.org/10.1007/978-3-319-50106-2

DOI

https://doi.org/10.1007/978-3-319-50106-2_20

Authors:

Alessio Arleo
Carla Binucci
Emilio Di Giacomo
William S. Evans
Luca Grilli
Giuseppe Liotta
Henk Meijer
Fabrizio Montecchiani
Sue Whitesides
Stephen Wismath

Publisher

Springer International Publishing

Sequence number

Premium Partner

Image Credits