## PIMS/SFU Computing Science DISTINGUISHED LECTURE SERIES 2006

- Date: 04/20/2006

Janos Pach (Courant Institute and City College)

Simon Fraser University

How to draw a Graph?

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.