Discrete Math Seminar: Steve Chaplick
Date
-
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.
