PIMS/SFU Computing Science DISTINGUISHED LECTURE SERIES 2006
Topic
How to draw a Graph?
Speakers
Details
Janos Pach received his M.S. and Ph.D. in Mathematics from Eotvos
University, Hungary, in 1977 and 1981 respectively. He is now a
Distinguished Professor of Mathematics at CUNY and a Research Professor
at the Courant Institute of Mathematics at NYU.
Prof. Pach has (co-)authored more than 250 journal papers, primarily in
combinatorics and discrete and computational geometry. He has received
many awards including the Grunwald Medal of the Bolyai Mathematical
Society in 1982, Ford Award from the Mathematical Association of
America, in 1990, Renyi Award from the Hungarian Academy of Sciences in
1993 and the Academy Award from the Hungarian Academy of Sciences in
1998. He is on the editorial boards of several journals including
Combinatorica (Springer), Computational Geometry: Theory and
Applications (Elsevier), Discrete and Computational Geometry
(Springer), Geombinatorics (Center for Excellence in Math. Education),
Graphs and Combinatorics (Springer), SIAM Journal of Discrete
Mathematics (SIAM), and Applied Mathematics Research eXpress (Hindawi).
Abstract: Almost all fields of application of computer science are full of problems whose solution involves drawing graphs in the plane (on the screen of a computer). Often there are constraints on the positions of the vertices (e.g., they must be at grid points) or of the edges (e.g., they must be drawn as straight-line segments). It is a vast area of research to find efficient drawing algorithms to achieve various objectives (small area, high resolution, minimum crossing number, etc.) without violating the constraints. Much of the research has been motivated by applications, including software engineering, CAD, database design, cartography, circuit schematics, automatic animation.
Does every planar graph of n vertices permit a straight-line drawing such that all vertices are represented by integer points of small coordinates? Is it true that the vertices of any planar graph can be represented by segments in the plane such that two segments cross each other if and only if the corresponding vertices are connected by an edge? Does every graph of maximum degree d permit a straight-line drawing, using edges of at most f(d) different slopes, where f(d) is a number depending only on d? We discuss problems of this type and describe some of the combinatorial, algebraic, and topological tools that may be relevant for their solution.
Abstract: Almost all fields of application of computer science are full of problems whose solution involves drawing graphs in the plane (on the screen of a computer). Often there are constraints on the positions of the vertices (e.g., they must be at grid points) or of the edges (e.g., they must be drawn as straight-line segments). It is a vast area of research to find efficient drawing algorithms to achieve various objectives (small area, high resolution, minimum crossing number, etc.) without violating the constraints. Much of the research has been motivated by applications, including software engineering, CAD, database design, cartography, circuit schematics, automatic animation.
Does every planar graph of n vertices permit a straight-line drawing such that all vertices are represented by integer points of small coordinates? Is it true that the vertices of any planar graph can be represented by segments in the plane such that two segments cross each other if and only if the corresponding vertices are connected by an edge? Does every graph of maximum degree d permit a straight-line drawing, using edges of at most f(d) different slopes, where f(d) is a number depending only on d? We discuss problems of this type and describe some of the combinatorial, algebraic, and topological tools that may be relevant for their solution.
Additional Information
Janos Pach (Courant Institute and City College)
