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 3dimensional visibility representation where
each vertex of the graph maps to a closed 2dimensional 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
nonzero 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 VRrepresentable.
I will discuss results about which types of graphs are
VRrepresentable. In particular, I will talk about planar graphs,
complete graphs, bipartite graphs, and tripartite graphs. In
addition, I will show that the family of VRrepresentable 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
Schedule for the Spring Semester:

 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 SpaceEfficient 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 3Dimensional 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
Document last modified on April 4, 1995