Universität zu Köln

Buchheim, Christoph ORCID: 0000-0001-9974-404X and Hong, Seok-Hee (2002). Crossing Minimization for Symmetries (Extended Abstract). In: Algorithms and Computation : 13th International Symposium, ISAAC 2002 Vancouver, BC, Canada, November 21-23, 2002 ; proceedings, pp. 137-152. Springer.

Preview

PDF zaik2002-440.pdf - Submitted Version Download (306kB) | Preview

Abstract

We consider the problem of drawing a graph with a given symmetry such that the number of edge crossings is minimal. We show that this problem is NP-hard, even if the order of orbits around the rotation center or along the reflection axis is fixed. Nevertheless, there is a linear time algorithm to test planarity and to construct a planar embedding if possible. Finally, we devise an O(m log m) algorithm for computing a crossing minimal drawing if inter-orbit edges may not cross orbits, showing in particular that intra-orbit edges do not contribute to the NP-hardness of the crossing minimization problem for symmetries. From this result, we can derive an O(m log m) crossing minimization algorithm for symmetries with an orbit graph that is a path.

Item Type:	Book Section
Creators:	Creators Email ORCID ORCID Put Code Buchheim, Christoph UNSPECIFIED https://orcid.org/0000-0001-9974-404X UNSPECIFIED Hong, Seok-Hee UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-548673
Title of Book:	Algorithms and Computation : 13th International Symposium, ISAAC 2002 Vancouver, BC, Canada, November 21-23, 2002 ; proceedings
Series Name:	Lecture notes in computer science
Volume:	2518
Page Range:	pp. 137-152
Date:	2002
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/54867