Lecture Notes in Computer Science

2 primary works

Research Problems in Discrete Geometry

by Peter Brac, William O J Moser, Janos Pach, and Peter Brass

Published 1 January 2005

This book is the result of a 25-year-old project and comprises a collection of more than 500 attractive open problems in the field. The largely self-contained chapters provide a broad overview of discrete geometry, along with historical details and the most important partial results related to these problems. This book is intended as a source book for both professional mathematicians and graduate students who love beautiful mathematical questions, are willing to spend sleepless nights thinking about them, and who would like to get involved in mathematical research.

Graph Drawing

by Janos Pach

Published 1 January 2005

The 12th International Symposium on Graph Drawing (GD 2004)was held d- ing September 29-October 2, 2004, at City College, CUNY, in the heart of Harlem, New York City. GD 2004 attracted 94 participants from 19 countries. In response to the call for papers, the program committee received 86 re- larsubmissionsdescribingoriginalresearchand/orsystemdemonstrations.Each submissionwasreviewedbyatleastthreeprogramcommitteemembersandc- ments were returned to the authors. Following extensive e-mail discussions, the program committee accepted 39 long papers (11 pages each in the proceedings) and 12 short papers (6 pages each). In addition, 4 posters were displayed and discussed in the conference exhibition room (2 pages each in the proceedings). Theprogramcommittee ofGD 2004invitedtwo distinguishedlecturers.P- fessorPaulSeymourfromPrincetonUniversitypresenteda newcharacterization ofclaw-freegraphs(jointworkwithMariaChudnovsky).ProfessorErikDemaine from MIT reported on his joint work with Fedor Fomin, MohammadTaghi - jiaghayi and Dimitrios Thilikos, concerning fast (often subexponential) ?x
- parameter algorithms and polynomial approximation schemes for broad classes of NP-hard problems in topological graph theory. A survey of the subject by Professors Demaine and Hajiaghayi is included in this volume. As usual, the annual graph drawing contest was held during the conference. This time the contest had two distinct tracks: the graph drawing challenge and the freestyle contest. A report is included in the proceedings.