Drawing plane graphs nicely |
| |
Authors: | Norishige Chiba Kazunori Onoguchi Takao Nishizeki |
| |
Affiliation: | (1) Department of Electrical Communications, Faculty of Engineering, Tohoku University, 980 Sendai, Japan |
| |
Abstract: | Summary This paper presents two efficient algorithms for drawing plane graphs nicely. Both draw all edges of a graph as straight line segments without crossing lines. The first draws a plane graph convex if possible, that is, in a way that every inner face and the complement of the outer face are convex polygons. The second, using the first, produces a pleasing drawing of a given plane graph that satisfies the following property as far as possible: the complements of 3-connected components, together with inner faces and the complement of the outer face, are convex polygons. The running time and storage space of both algorithms are linear in the number of vertices of the graph. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|