# New results on a visibility representation of graphs in 3D

Fekete, Sandor P. and Houle, Michael and Whitesides, Sue
(1996)
*New results on a visibility representation of graphs in 3D.*
**Published In:**
Graph drawing : Symposium on Graph Drawing, GD '95, Passau, Germany, September 20 - 22, 1995 ; proceedings, Lecture notes in computer science. 1027 Springer 1996, pp. 234-241.

## Abstract

This paper considers a 3-dimensional visibility representation of cliques Kn. In this representation, the objects representing the vertices are 2-dimensional and lie parallel to the x,y-plane, and two vertices of the graph are adjacent if and only if their corresponding objects see each other by a line of sight parallel to the z-axis that intersects the interiors of the objects. In particular, we represent vertices by unit discs and by discs of arbitrary radii (possibly different for different vertices); we also represent vertices by axis-aligned unit squares, by axis-aligned squares of arbitrary size (possibly different for different vertices), and by axis-aligned rectangles. We present: a significant improvement (from 102 to 55) of the best known upper bound for the size of cliques representable by rectangles or squares of arbitrary size; a sharp bound for the representation of cliques by unit squares (K7 can be represented but Kn for n>7 cannot); a representation of Kn by unit discs.

Download: |
Postscript
- Preprinted Version
Download (193kB) | Preview |
---|---|

Export as: | [error in script] |

Editorial actions: |
View Item (Login required) |

ZAIK Number: | [error in script] |
---|---|

Depositing User: | Archive Admin |

Date Deposited: | 02 Apr 2001 00:00 |

Last Modified: | 19 Dec 2011 09:46 |

URI: | http://e-archive.informatik.uni-koeln.de/id/eprint/207 |