nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

Visibility Representations of Boxes in 2.5 Dimensions

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

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 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 \).

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 Low Ply Drawings of Trees

Nächstes Kapitel The Partial Visibility Representation Extension Problem

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)

Titel: Visibility Representations of Boxes in 2.5 Dimensions
verfasst von: Alessio Arleo
Carla Binucci
Emilio Di Giacomo
William S. Evans
Luca Grilli
Giuseppe Liotta
Henk Meijer
Fabrizio Montecchiani
Sue Whitesides
Stephen Wismath
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_20

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"