Buchheim, Christoph ORCID: 0000-0001-9974-404X and Hong, Seok-Hee (2008). Testing Planarity of Geometric Automorphisms in Linear Time. Algorithmica, 52 (4). pp. 448-465. Springer.

[img]
Preview
 PDF
zaik2006-517.pdf - Draft Version
Download (304kB) | Preview

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.

Item Type: Journal Article
Creators:
CreatorsEmailORCIDORCID Put Code
Buchheim, ChristophUNSPECIFIEDorcid.org/0000-0001-9974-404XUNSPECIFIED
Hong, Seok-HeeUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
URN: urn:nbn:de:hbz:38-548953
Journal or Publication Title: Algorithmica
Volume: 52
Number: 4
Page Range: pp. 448-465
Date: 2008
Publisher: Springer
Language: English
Faculty: Faculty of Mathematics and Natural Sciences
Divisions: Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects: Data processing Computer science
Refereed: No
URI: http://kups.ub.uni-koeln.de/id/eprint/54895

Downloads

Downloads per month over past year

Export

Actions (login required)

View Item View Item