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.


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


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)