To represent a graph by a nice geometric picture is a natural goal in itself, but in addition it is an important tool in the study of various graph properties and in the design of graph algorithms. We survey several forms of this interplay between graph algorithms and geometry: algorithms for perfect graphs, maximum cut, connectivity, bandwidth. We discuss how to use a representation obtained from the adjacency matrix to compute an almost optimal weak regularity partition in constant time in the property testing model.

László Lovász is a Hungarian–American mathematician, best known for his work in combinatorics, for which he was awarded the Wolf Prize and the Knuth Prize in 1999, and the Kyoto Prize in 2010.

Lovász received his Candidate of Sciences degree in 1970 at Hungarian Academy of Sciences. His advisor was Tibor Gallai.

Until 1975, Lovász worked at the Eötvös University, between 1975–1982, he led the Department of Geometry at the University of Szeged. In 1982, he returned to the Eötvös University, where he created the Department of Computer Science. The former and current scientists of the department include György Elekes, András Frank, József Beck, Éva Tardos, András Hajnal, Lajos Pósa, Miklós Simonovits, Tamás Szőnyi.

Lovász was a professor at Yale University during the 1990s and was a collaborative member of the Microsoft Research Center until 2006. He returned to Eötvös Loránd University, Budapest, where he was the director of the Mathematical Institute (2006–2011).

He served as president of the International Mathematical Union between January 1, 2007 and December 31, 2010.

Lovász wrote 6 papers with Paul Erdős, a mathematician who was famous for writing papers with co-authors, which earned Lovász an Erdős number of one.