Feedback
Seminars
Upcoming Seminars:
Select which seminar you are interested in:
- CSC Seminar
- Discrete Math Seminar
- Number Theory Seminar
- Operations Research Seminar
- Seminar on Teaching Mathematics
- Global Warming Spring 2011 Seminar Series: A Science Perspective
Discrete Math Seminars
Discrete Math seminar: Steve Chaplick
Tuesday, May 22 - 2:30pm to 3:30pm
Title: Bend-Bounded Path Intersection Graphs: Sausages, Noodles, and Waffles on a Grill
Abstract:
In this paper we study properties of intersection graphs of k-bend paths in the rectangular grid. A k-bend path is a path with at most k 90-degree turns. The class of graphs representable by intersections of k-bend paths is denoted by B_k-VPG. We show here that forevery fixed k, B_k-VPG is a strict subset of B_{k+1}-VPG and that recognition of graphs from B_k-VPG is NP-complete even when the input graph is givenby a B_{k+1}-VPG representation. We also show that the class B_k-VPG (for k≥ 1) is in no inclusion relation with the class of intersection graphs of straight line segments in the plane.
This is joint work with Vit Jelinek, Jan Kratochvil, and Tomas Vyskocil.
Abstract:
In this paper we study properties of intersection graphs of k-bend paths in the rectangular grid. A k-bend path is a path with at most k 90-degree turns. The class of graphs representable by intersections of k-bend paths is denoted by B_k-VPG. We show here that forevery fixed k, B_k-VPG is a strict subset of B_{k+1}-VPG and that recognition of graphs from B_k-VPG is NP-complete even when the input graph is givenby a B_{k+1}-VPG representation. We also show that the class B_k-VPG (for k≥ 1) is in no inclusion relation with the class of intersection graphs of straight line segments in the plane.
This is joint work with Vit Jelinek, Jan Kratochvil, and Tomas Vyskocil.
Discrete Math seminar: Tamon Stephen
Tuesday, May 29 - 2:30pm to 3:30pm
Discrete Math seminar: Petr Škoda
Tuesday, Jun 12 - 2:30pm to 3:30pm
Discrete Math seminar: Ryuhei Uehara
Tuesday, Jun 19 - 2:30pm to 3:30pm