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.


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.

Download: [img] Postscript - Preprinted Version
Download (790kB) | Preview
Download: [img] PDF - Preprinted Version
Download (304kB) | Preview
Editorial actions: View Item View Item (Login required)
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