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: [img] Postscript - Preprinted Version
Download (790kB) | Preview
Download: [img] PDF - Preprinted Version
Download (304kB) | Preview
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Article
Citations: 0 (Google Scholar) | 0 (Web of Science)
Uncontrolled Keywords: graph drawing automorphisms symmetries planarity
Subjects:
  • 05-XX Combinatorics > 05Cxx Graph theory > 05C85 Graph algorithms

  • 20-XX Group theory and generalizations > 20Bxx Permutation groups > 20B25 Finite automorphism groups of algebraic, geometric, or combinatorial structures

    		•
    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