3D Visibility Representations by Regular Polygons

Stola, Jan (2010) 3D Visibility Representations by Regular Polygons. In: Graph Drawing 17th International Symposium, GD 2009, September 22-25, 2009, Chicago, IL, USA , pp. 323-333 (Official URL: http://dx.doi.org/10.1007/978-3-642-11805-0_31).

Full text not available from this repository.

Abstract

We study 3D visibility representations of complete graphs where vertices are represented by equal regular polygons lying in planes parallel to the xy-plane. Edges correspond to the z-parallel visibility among these polygons. We improve the upper bound on the maximum size of a complete graph with a 3D visibility representation by regular n-gons from 2O(n) to O(n4 ).

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-11805-0_31
Classifications:P Styles > P.900 Visibility
Z Theory > Z.250 Geometry
P Styles > P.060 3D
ID Code:1109

Repository Staff Only: item control page

References

Stola, J.: 3D Visibility Representations of Complete Graphs. In: Liotta, G. (ed.) GD 2003. LNCS, vol. 2912, pp. 226–237. Springer, Heidelberg (2004)

Babilon, R., Nyklová, H., Pangrác, O., Vondrák, J.: Visibility Representations of Complete Graphs. In: Kratochvíl J. (ed.) GD 1999. LNCS, vol. 1731, pp. 333–340. Springer, Heidelberg (1999)

Fekete, S.P., Houle, M.E., Whitesides, S.: New Results on a Visibility Representation of Graphs in 3D. In: Brandenburg, F.J. (ed.) GD 1995. LNCS, vol. 1027, pp. 234–241. Springer, Heidelberg (1996)

Bose, P., Everett, H., Fekete, S.P., Lubiw, A., Meijer, H., Romanik., K., Shermer, T., Whitesides, S.: On a visibility representation for graphs in three dimensions. In: Di Battista, G., Eades, P., de Fraysseix, H., Rosenstiehl, P., Tamassia, R. (eds.) GD 1993, pp. 38–39 (1993)

Stola, 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)

Fekete, S.P., Meijer, H.: Rectangle and box visibility graphs in 3D. Int. J. Comput. Geom. Appl. 97, 1–28 (1997)

Tamassia, R., Tollis, I.G.: A unifed approach to visibility representations of planar graphs. Discrete and Computational Geometry 1, 321–341 (1986)

Dean, A.M., Hutchinson, J.P.: Rectangle-Visibility Representations of Bipartite Graphs. In: Tamassia, R., Tollis, I.G. (eds.) GD 1994. LNCS, vol. 894, pp. 159– 166. Springer, Heidelberg (1995)

Erdös, P., Szekeres, G.: A combinatorial problem in geometry. Compositio Math. 2, 463–470 (1935)

Ramsey, F.P.: On a problem of formal logic. Proc. London Math. Soc. 30, 264–286 (1930)

Graham, R., Rothschild, B., Spencer, J.: Ramsey Theory, 2nd edn. Wiley-Interscience Series in Discrete Mathematics. Wiley, New York (1990)