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.

Includes supplementary material: sn.pub/extras

Inhalt
Papers.- Reconfiguring Triangulations with Edge Flips and Point Moves.- Drawing Power Law Graphs.- Hexagonal Grid Drawings: Algorithms and Lower Bounds.- Improved Bounds for the Number of (? k)-Sets, Convex Quadrilaterals, and the Rectilinear Crossing Number of K n .- On the Realizable Weaving Patterns of Polynomial Curves in .- Drawing the AS Graph in 2.5 Dimensions.- Boundary Labeling: Models and Efficient Algorithms for Rectangular Maps.- Convex Drawings of 3-Connected Plane Graphs.- Partitions of Complete Geometric Graphs into Plane Trees.- Additional PC-Tree Planarity Conditions.- GraphML Transformation.- Clustering Cycles into Cycles of Clusters.- Unit Bar-Visibility Layouts of Triangulated Polygons.- Really Straight Graph Drawings.- Layouts of Graph Subdivisions.- Label Number Maximization in the Slider Model.- An Efficient Implementation of Sugiyama's Algorithm for Layered Graph Drawing.- Random Geometric Graph Diameter in the Unit Disk with ? p Metric.- Algorithms for Drawing Media.- Confluent Layered Drawings.- Simultaneous Embedding of Planar Graphs with Few Bends.- A Fast and Simple Heuristic for Constrained Two-Level Crossing Reduction.- Contact and Intersection Representations.- Dynamic Graph Drawing of Sequences of Orthogonal and Hierarchical Graphs.- Graph Drawing by Stress Majorization.- Computing Radial Drawings on the Minimum Number of Circles.- Hamiltonian-with-Handles Graphs and the k-Spine Drawability Problem.- Distributed Graph Layout for Sensor Networks.- Drawing Large Graphs with a Potential-Field-Based Multilevel Algorithm.- Building Blocks of Upward Planar Digraphs.- A Linear Time Algorithm for Constructing Maximally Symmetric Straight-Line Drawings of Planar Graphs.- Train Tracks and Confluent Drawings.- The Three DimensionalLogic Engine.- Long Alternating Paths in Bicolored Point Sets.- Intersection Reverse Sequences and Geometric Applications.- New Exact Results and Bounds for Bipartite Crossing Numbers of Meshes.- Drawing Pfaffian Graphs.- 3D Visualization of Semantic Metadata Models and Ontologies.- A Note on the Self-similarity of Some Orthogonal Drawings.- No-Three-in-Line-in-3D.- Visual Navigation of Compound Graphs.- Layout Volumes of the Hypercube.- New Theoretical Bounds of Visibility Representation of Plane Graphs.- Software Demonstrations.- Visualizing Large Graphs with Compound-Fisheye Views and Treemaps.- A Compound Graph Layout Algorithm for Biological Pathways.- Curvilinear Graph Drawing Using the Force-Directed Method.- Graphael: A System for Generalized Force-Directed Layouts.- QUOGGLES: Query On Graphs A Graphical Largely Extensible System.- Visualisation of Large and Complex Networks Using PolyPlane.- The Metro Map Layout Problem.- An Interactive Multi-user System for Simultaneous Graph Drawing.- Posters.- Gravisto: Graph Visualization Toolkit.- DNA Secondary Structures for Probe Design.- Open Problems Wiki.- Visualization and ILOG CPLEX.- Graph Drawing Contest.- Graph-Drawing Contest Report.- Invited Talk.- Fast Algorithms for Hard Graph Problems: Bidimensionality, Minors, and Local Treewidth.