Get an In-Depth Understanding of Graph Drawing Techniques, Algorithms, Software, and Applications
The Handbook of Graph Drawing and Visualization provides a broad, up-to-date survey of the field of graph drawing. It covers topological and geometric foundations, algorithms, software systems, and visualization applications in business, education, science, and engineering. Each chapter is self-contained and includes extensive references.
The first several chapters of the book deal with fundamental topological and geometric concepts and techniques used in graph drawing, such as planarity testing and embedding, crossings and planarization, symmetric drawings, and proximity drawings. The following chapters present a large collection of algorithms for constructing drawings of graphs, including tree, planar straight-line, planar orthogonal and polyline, spine and radial, circular, rectangular, hierarchical, and three-dimensional drawings as well as labeling algorithms, simultaneous embeddings, and force-directed methods. The book then introduces the GraphML language for representing graphs and their drawings and describes three software systems for constructing drawings of graphs: OGDF, GDToolkit, and PIGALE. The final chapters illustrate the use of graph drawing methods in visualization applications for biological networks, computer security, data analytics, education, computer networks, and social networks.
Edited by a pioneer in graph drawing and with contributions from leaders in the graph drawing research community, this handbook shows how graph drawing and visualization can be applied in the physical, life, and social sciences. Whether you are a mathematics researcher, IT practitioner, or software developer, the book will help you understand graph drawing methods and graph visualization systems, use graph drawing techniques in your research, and incorporate graph drawing solutions in your products.
Table of Contents
Planarity Testing and Embedding Maurizio Patrignani
Crossings and Planarization Christoph Buchheim, Markus Chimani, Carsten Gutwenger, Michael Jünger, and Petra Mutzel
Symmetric Graph Drawing Peter Eades and Seok-Hee Hong
Proximity Drawings Giuseppe Liotta
Tree Drawing Algorithms Adrian Rusu
Planar Straight-Line Drawing Algorithms Luca Vismara
Planar Orthogonal and Polyline Drawing Algorithms Christian A. Duncan and Michael T. Goodrich
Spine and Radial Drawings Emilio Di Giacomo, Walter Didimo, and Giuseppe Liotta
Circular Drawing Algorithms Janet M. Six and Ioannis G. Tollis
Rectangular Drawing Algorithms Takao Nishizeki and Md. Saidur Rahman
Simultaneous Embedding of Planar Graphs Thomas Bläsius, Stephen G. Kobourov, and Ignaz Rutter
Force-Directed Drawing Algorithms Stephen G. Kobourov
Hierarchical Drawing Algorithms Patrick Healy and Nikola S. Nikolov
Three-Dimensional Drawings Vida Dujmović and Sue Whitesides
Labeling Algorithms Konstantinos G. Kakoulis and Ioannis G. Tollis
Graph Markup Language (GraphML) Ulrik Brandes, Markus Eiglsperger, Jürgen Lerner, and Christian Pich
The Open Graph Drawing Framework (OGDF) Markus Chimani, Carsten Gutwenger, Michael Jünger, Gunnar W. Klau, Karsten Klein, and Petra Mutzel
GDToolkit Giuseppe Di Battista and Walter Didimo
PIGALE Hubert de Fraysseix and Patrice Ossona de Mendez
Biological Networks Christian Bachmaier, Ulrik Brandes, and Falk Schreiber
Computer Security Olga Ohrimenko, Charalampos Papamanthou, and Bernardo Palazzi
Graph Drawing for Data Analytics Stephen G. Eick
Graph Drawing and Cartography Alexander Wolff
Graph Drawing in Education Stina Bridgeman
Computer Networks Giuseppe Di Battista and Massimo Rimondini
Social Networks Ulrik Brandes, Linton C. Freeman, and Dorothea Wagner
Roberto Tamassia is the Plastech Professor of Computer Science, Chair of the Department of Computer Science, and Director of the Center for Geometric Computing at Brown University. He is a fellow of the American Association for the Advancement of Science (AAAS), the Association for Computing Machinery (ACM), and the Institute of Electrical and Electronics Engineers (IEEE). He received a Technical Achievement Award from the IEEE Computer Society for pioneering the field of graph drawing. Dr. Tamassia is the co-founder and co-editor-in-chief of the Journal of Graph Algorithms and Applications. He has published six textbooks and more than 250 research articles and books. He received a PhD in electrical and computer engineering from the University of Illinois at Urbana-Champaign and a Laurea in electrical engineering from the "Sapienza" University of Rome. His research interests include the analysis, design, and implementation of algorithms, applied cryptography, cloud computing, computational geometry data security, and graph drawing.
"In the topological and geometric foundations to graph drawing, this collection goes beyond defining planarity or even minimizing edge crossings, discussing also spine, radial, circular, tree, and rectangular drawing definitions and algorithms. There is much content on formally defining and approaching such subjective and even aesthetic areas as legibility in name placement and labeling, as well as maximizing pleasing symmetries and other methods related to edge lengths and linearity that research has shown to impart information to humans effectively. Many chapters touch on history and open problems in this well-arranged compendium weighted toward content ripe for practical implementation."
—Tom Schulte, MAA Reviews, February 2014
"This handbook fills an important need. It is an impressive compendium of research in the booming field of graph drawing and visualization: algorithms, layout strategies, and software for diverse problem domains. It’s great to have all these resources in one place, showing the vibrant activity in graph drawing and visualization. The book lays a foundation for the next generation of research breakthroughs. Whether you drill down or go wide, you’ll learn something useful. You’ll see how effectively designed network visualizations can produce powerful insights in many fields."
—Prof. Ben Shneiderman, University of Maryland
"This handbook is the most comprehensive reference on graph drawing I have ever seen. It is an indispensable aid to programmers, engineers, students, teachers, and researchers who create or use algorithms and systems for visualizing networks and abstract graphs. It covers the theory and practice in core topics and related areas, such as labeling, programming frameworks, and applications in network analysis. It’s an amazing compendium of almost everything known about practical graph drawing."
—Stephen North, Executive Director and Co-Founder of graphviz.org
"After two decades of annual graph drawing conferences, the field is sufficiently developed to warrant this nearly 900-page Handbook. All constituencies are well-served. New researchers can become quickly oriented to the field through the opening foundational chapters. Practitioners can find algorithms to suit their needs in the heart of the handbook: ten chapters on a wealth of algorithms, usefully organized into intuitive categories: from planar algorithms to three-dimensional drawings, passing through the natural restrictions—radial, rectangular, circular, polyline—and from hierarchical to force-directed.
Many algorithms are now incorporated into graph-drawing software packages, and all the major packages are described in chapters by their developers. The key application areas are surveyed, some to be expected—biological networks, social networks, cartography—and some less obvious but no less active, e.g., education and computer security. All chapters are authored by the leaders of the field and edited into a pleasing common style.
The field of graph drawing remains dynamic, as testified by the many open problems collected in the chapters, from turning Mani’s theorem into an algorithm for 3-connected planar graphs, to deciding whether every degree-6 graph has a 2-bend orthogonal drawing in 3D. It is an achievement to so thoroughly cover the range from theory to algorithms to software to applications, and I expect the Handbook to serve as the key resource for researchers in the field."
—Joseph O’Rourke, Smith College