Séminaire Algo - Martin Charles Golumbic
Il y a: 231 days
Martin Charles Golumbic
The Elusive Nature of Intersecting Paths on a Grid
Salle de séminaire (4B05R) - Bâtiment Copernic
In this lecture, we will survey the mathematical and algorithmic results on the edge intersection graphs of paths in a grid (EPG) together with several restrictions on the representations. Two important restrictions that are motivated by network and circuit design problems are:
(1) allowing just a single bend in any path, and
(2) limiting the paths within a rectangular grid with the endpoints of each path on the boundary of the rectangle.
Golumbic, Lipshteyn and Stern introduced EPG graphs in 2005, proving that every graph is an EPG graph, and then turning their attention to the subclass of graphs that admit an EPG representation in which every path has at most a single bend, called B1 -EPG graphs. They proved that any tree is a B1 -EPG graph and gave a structural property that enables generating non B1 -EPG graphs. A characterization of the representation of cliques and chordless 4-cycles in B1 -EPG graphs was given, and also prove that single bend paths on a grid have Strong Helly number 4, and when the paths satisfy the usual Helly property, they have Strong Helly number 3. Subsequent results by our colleagues will be surveyed, as well as open problems and future work.
We then present our new work on boundary generated B1 -EPG graphs together with Gila Morgenstern and Deepak Rajendraprasad. For two boundary vertices u and v on two adjacent boundaries of a rectangular grid G, we call the unique single-bend path connecting u and v in G using no other boundary vertex of G as the path generated by (u, v). A path in G is called boundary-generated, if it is generated by some pair of vertices on two adjacent boundaries of G. In this work, we study the edge-intersection graphs of boundary-generated paths on a grid or ∂EPGgraphs.
We show that ∂EPGgraphs can be covered by two collections of vertex-disjoint cobipartite chain graphs. This leads us to a linear-time testable characterization of ∂EPGtrees and also a tight upper bound on the equivalence covering number of general ∂EPGgraphs. We also study the cases of two-sided ∂EPGand three-sided ∂EPGgraphs, which are respectively, the subclasses of ∂EPGgraphs obtained when all the boundary vertex pairs which generate the paths are restricted to lie on at most two or three boundaries of the grid. For the former case, we give a complete characterization. We do not know yet whether one can efficiently recognize ∂EPGgraphs. Though the problem is linear-time solvable on trees, we suspect that it might be NP-hard in general.