Bold graph drawings |
| |
Authors: | Marc van Kreveld |
| |
Affiliation: | Department of Information and Computing Sciences, Utrecht University, The Netherlands |
| |
Abstract: | When a graph is drawn in a classical manner, its vertices are shown as small disks and its edges with a positive width; zero-width edges and zero-size vertices exist only in theory. Let r denote the radius of the disks that show vertices and w the width of edges. We give a list of conditions that make such a drawing good and that apply to not necessarily planar graphs. We show that if r<w, a vertex must have constant degree for a drawing to satisfy the conditions, and if r?w, a vertex can have any degree. We also give an algorithm that, for a given drawing and values for r and w, determines whether the bold drawing satisfies the conditions. Furthermore, we show how to maximize r and/or w without violating the conditions in polynomial time. |
| |
Keywords: | Graph drawing Edge and vertex size Planar straight-line drawing |
本文献已被 ScienceDirect 等数据库收录! |
|