A Linear Time Algorithm for Constructing Maximally Symmetric Straight Line Drawings of Triconnected Planar Graphs |
| |
| Authors: | Seok-Hee Hong Brendan McKay Peter Eades |
| |
| Institution: | (1) School of Information Technologies, University of Sydney, Sydney, NSW 2006 and National ICT Australia, Eveleigh, NSW 1430, Australia;(2) Department of Computer Science, Australian National University, Canberra, ACT 0200, Australia |
| |
| Abstract: | Symmetry is one of the most important aesthetic criteria in graph drawing because it reveals structure in the graph. To draw
graphs symmetrically, we employ two steps. The first step is to find appropriate automorphisms. The second step is to draw
the graph to display the automorphisms. Our aim in this paper is to construct maximally symmetric straight line drawings of
triconnected planar graphs in linear time. Previously known algorithms run in quadratic time. We show that an algorithm of
Fontet can be used to find an embedding in the plane with the maximum number of symmetries, and present a new algorithm for
finding a straight line drawing that achieves that maximum. Both algorithms run in linear time. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
