DIMACS Seminar on Theoretical Computer Science

Title:

A Three Dimensional Visibility Representation for Graphs

Speaker:

Kathleen Romanik

Place:

CoRE Building, Seminar Room 431

Busch Campus, Rutgers University

Time:

10:00 AM

Wednesday, April 12, 1995

Abstract:

Visibility representations of graphs map vertices to sets in Euclidean space and express edges as visibility relations between these sets. This research studies a 3-dimensional visibility representation where each vertex of the graph maps to a closed 2-dimensional rectangle in $R^3$ such that the rectangles are disjoint, the planes determined by the rectangles are perpendicular to the $z$-axis, and the sides of the rectangles are parallel to the $x$ or $y$ axes. Edges are expressed by the following visibility relation. Two rectangles $R_i$ and $R_j$ are considered visible provided that there exists a closed cylinder $C$ of non-zero length and radius such that the ends of $C$ are contained in $R_i$ and $R_j$, the axis of $C$ is parallel to the $z$-axis, and $C$ does not intersect any other rectangle. If a graph can be represented in this way, then the graph is VR-representable.

I will discuss results about which types of graphs are VR-representable. In particular, I will talk about planar graphs, complete graphs, bipartite graphs, and tripartite graphs. In addition, I will show that the family of VR-representable graphs is not closed under graph minors, and I will give a result concerning the dimension of this class of graphs.

Joint work with:

Prosenjit Bose - University of British Columbia
Hazel Everett - Universite du Quebec a Montreal
Sandor Fekete - University of Koeln
Anna Lubiw - University of Waterloo
Henk Meijer - Queens University
Tom Shermer - Simon Fraser University
Sue Whitesides - McGill University

Jan. 25: Sridhar Rajagopalan: On the value of Planning and Capital
Feb. 1: Neal Young: Randomized Rounding Without Solving the Linear Program
Feb. 8: Richard Lipton: Speeding Up Computations via Molecular Biology
Feb. 15: no meeting; but note the DIMACS Complexity day, Feb. 17
Feb. 22: Shiyu Zhou: Explicit Dispersers with Polylog Degree
Mar. 1: Bhaskar DasGupta: Analog versus Discrete Neural Networks
Mar. 8: no meeting
Mar. 22: Eric Allender: Sparse Hard Sets for P Give Space-Efficient Algorithms
Mar. 29: Robert Beals: Symmetric Logspace is Closed Under Complement
Apr. 5: no meeting; but note Columbia University's Theory Day, April 7
Apr. 12: Kathleen Romanik: A 3-Dimensional Visibility Representation for Graphs
Apr. 19:
Apr. 26:
May 3:
May 10: Rajeev Alur: Timed Automata
May 17: Mikkel Thorup: An O(log log n) Priority Queue