String Graphs and Paths on a Grid

演讲人: Prof.Martin Charles Golumbic University of Haifa, Israel
时间: 2015-05-14 13:30-2015-05-14 14:30
地点:Room 102, Tsinghua Xuetang

After a brief introduction, we will report on recent work on the intersection graphs of k-bend paths on a grid, the so called Bk ─VPG graphs. For example, in chip manufacturing, circuit layout is modeled as paths (wires) on a grid, where  it is natural to constrain the number of bends per wire for reasons of feasibility and to reduce the cost of the chip. If the number k of bends is not restricted, then the VPG graphs are equivalent to the well-known class of string graphs, namely,

In the case of B0 ─VPG graphs, we observe that horizontal and vertical segments have strong Helly number 2, and thus the clique problem has polynomial-time complexity, given the path representation. The recognition and coloring problems for B0 ─VPG graphs, however, are NP-complete. We give a 2-approximation algorithm for coloring them. Furthermore, we prove that triangle-free B0 ─VPG graphs are 4-colorable, and this is best possible.

There is a hierarchy of VPG graphs relating them to other known families of graphs. The grid intersection graphs of Bellantoni, et al. and Hartman/Newman are shown to be equivalent to the bipartite B0 ─VPG graphs and the circle graphs are strictly contained in B1 ─VPG graphs. We also relate these to planar graphs, cographs and other structured families.


Martin Charles Golumbic is Professor of Computer Science and Director of the Caesarea Edmond Benjamin de Rothschild Institute for Interdisciplinary Applications of Computer Science at the University of Haifa. He is the founding Editor-in-Chief of the journal “Annals of Mathematics and Artificial Intelligence” and is or has been a member of the editorial boards of several other journals including “Discrete Applied Mathematics”, “Constraints” and “AI Communications”. His current area of research is in combinatorial mathematics interacting with real world problems in computer science and artificial intelligence. 

Professor Golumbic received his Ph.D. in mathematics from Columbia University in 1975 under the direction of Samuel Eilenberg. He has held positions at the Courant Institute of Mathematical Sciences of New York University, Bell Telephone Laboratories, the IBM Israel Scientific Center and Bar-Ilan University. He has also had visiting appointments at the Université de Paris, the Weizmann Institute of Science, Ecole Polytechnique Fédérale de Lausanne, Universidade Federal do Rio de Janeiro, Rutgers University, Columbia University, Hebrew University and Tsinghua University.

He is the author of the book  “Algorithmic Graph Theory and Perfect Graphs”, coauthor of a second book “Tolerance Graphs” and has written many research articles in the areas of combinatorial mathematics, algorithmic analysis, expert systems, artificial intelligence, and programming languages. He has been a guest editor of special issues of several journals, the editor of the books “Advances in Artificial Intelligence, Natural Language and Knowledge-based Systems”, and “Graph Theory, Combinatorics and Algorithms: Interdisciplinary Applications”. His most recent book is “Fighting Terror Online: The Convergence of Security, Technology, and the Law”, published by Springer-Verlag.

Prof. Golumbic and was elected as Foundation Fellow of the Institute of Combinatorics and its Applications in 1995, and has been a Fellow of the European Artificial Intelligence society ECCAI since 2005.  He is a member of the Academia Europaea, honoris causa -- elected 2013. Martin Golumbic has been the chairman of over fifty national and international symposia. He a member of the Phi Beta Kappa, Pi Mu Epsilon, Phi Kappa Phi, Phi Eta Sigma honor societies and is married and the father of four bilingual, married daughters and has four granddaughters and five grandsons.