1st Edition

Handbook of Graph Drawing and Visualization

Edited By Roberto Tamassia Copyright 2014
    866 Pages 480 B/W Illustrations
    by Chapman & Hall

    866 Pages 480 B/W Illustrations
    by Chapman & Hall

    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.

    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

    Index

    Biography

    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