Graph Drawing

Authored by: Roberto Tamassia , Giuseppe Liotta

Discrete and Computational Geometry

Print publication date:  April  2004
Online publication date:  April  2004

Print ISBN: 9781584883012
eBook ISBN: 9781420035315
Adobe ISBN:

10.1201/9781420035315.ch52

 Download Chapter

 

Abstract

Graph drawing addresses the problem of constructing geometric representations of graphs, and has important applications to key computer technologies such as software engineering, database systems, visual interfaces, and computer-aided design. Research on graph drawing has been conducted within several diverse areas, including discrete mathematics (topological graph theory, geometric graph theory, order theory), algorithmics (graph algorithms, data structures, computational geometry, vlsi), and human-computer interaction (visual languages, graphical user interfaces, software visualization). This chapter overviews aspects of graph drawing that are especially relevant to computational geometry. Basic definitions on drawings and their properties are given in Section 52.1. Bounds on geometric and topological properties of drawings (e.g., area and crossings) are presented in Section 52.2. Section 52.3 deals with the time complexity of fundamental graph drawing problems. An example of a drawing algorithm is given in Section 52.4. General techniques for drawing graphs are surveyed in Section 52.5. Section 52.6 covers selected topics that have recently attracted considerable research interest.

 Cite
Search for more...
Back to top

Use of cookies on this website

We are using cookies to provide statistics that help us give you the best experience of our site. You can find out more in our Privacy Policy. By continuing to use the site you are agreeing to our use of cookies.