# Discrete Math Seminar: Steve Chaplick

## Topic

Bend-Bounded Path Intersection Graphs: Sausages, Noodles, and Waffles on a Grill

## Speakers

## Details

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.

## Additional Information

This is a Past Event

Event Type

**Scientific, Seminar**

Date

**May 22, 2012**

Time

**-**

Location

Simon Fraser University