Drawing Graphs: Methods And Models

Lecture Notes in Computer Science Edited by G. Goos, J. Hartmanis and J. van Leeuwen 2025 3 Berlin Heidelberg New York Barcelona Hong Kong London Milan Paris Singapore Tokyo Michael Kaufmann Dorothea Wagner (Eds.) Drawing Graphs Methods and Models 13 Series Editors Gerhard Goos, Karlsruhe University, Germany Juris Hartmanis, Cornell University, NY, USA Jan van Leeuwen, Utrecht University, The Netherlands Volume Editors Michael Kaufmann University of Tübingen, Wilhelm Schickard Institute for Computer Science Sand 13, 72076 Tübingen, Germany E-mail: [email protected] Dorothea Wagner University of Konstanz, Department of Computer & Information Science Box D 188, 78457 Konstanz, Germany E-mail: [email protected] Cataloging-in-Publication Data applied for Die Deutsche Bibliothek - CIP-Einheitsaufnahme Drawing graphs : methods and models / Michael Kaufmann ; Dorothea Wagner (ed.). - Berlin ; Heidelberg ; New York ; Barcelona ; Hong Kong ; London ; Milan ; Paris ; Singapore ; Tokyo : Springer, 2001 (Lecture notes in computer science ; 2025) ISBN 3-540-42062-2 CR Subject Classification (1998): G.2, I.3, F.2 ISSN 0302-9743 ISBN 3-540-42062-2 Springer-Verlag Berlin Heidelberg New York This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting, reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer-Verlag. Violations are liable for prosecution under the German Copyright Law. Springer-Verlag Berlin Heidelberg New York a member of BertelsmannSpringer Science+Business Media GmbH http://www.springer.de © Springer-Verlag Berlin Heidelberg 2001 Printed in Germany Typesetting: Camera-ready by author, data conversion by Boller Mediendesign Printed on acid-free paper SPIN: 10782379 06/3142 543210 Preface Drawings are an attractive and effective way of conveying information. Graph Drawing includes all aspects of visualizing structural relations between objects. The range of topics extends from graph algorithms, graph theory, geometry and topology, to visual languages, visual perception, and information visualization, and to computer-human interaction and graphics design. Clearly, the design of appropriate drawings is a complex and costly task where automation is urgently required. The automated generation of graph drawings has important applications in many areas of computer sc