Pacific Institute for the Mathematical Sciences - PIMS

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.