Testing Planarity of Geometric Automorphisms in Linear Time
Buchheim, Christoph and Hong, Seok-Hee
(2008)
Testing Planarity of Geometric Automorphisms in Linear Time.
Published in:
Algorithmica Vol. 52 (4).
pp. 448-465.
Abstract
It is a well-known result that testing a graph for planarity and, in the affirmative case, computing a planar embedding can be done in linear time. In this paper, we show that the same holds if additionally we require that the produced drawing be symmetric with respect to a given automorphism of the graph. This problem arises naturally in the area of automatic graph drawing, where symmetric and planar drawings are desired whenever possible.
Actions:
Download: |
Download (790kB) | Preview |
---|---|
Download: |
Download (304kB) | Preview |
Editorial actions: | ![]() |
Content information:
Item Type: | Article |
---|---|
Citations: | 0 (Google Scholar) | 0 (Web of Science) |
Uncontrolled Keywords: | graph drawing automorphisms symmetries planarity |
Subjects: |
|
Divisions: | Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger |
Related URLs: |
Deposit Information:
ZAIK Number: | zaik2006-517 |
---|---|
Depositing User: | Christoph Buchheim |
Date Deposited: | 21 Dec 2007 00:00 |
Last Modified: | 09 Jan 2012 15:53 |
URI: | http://e-archive.informatik.uni-koeln.de/id/eprint/517 |