You are viewing a javascript disabled version of the site. Please enable Javascript for this site to function properly.
Go to headerGo to navigationGo to searchGo to contentsGo to footer
In content section. Select this link to jump to navigation

A Note on the Median Heuristic for Drawing Bipartite Graphs

Article type: Research Article

Authors: Mäkinen, Erkki

Affiliations: University of Tampere, Department of Computer Science, P.O. Box 607, SF-33101 Tampere, Finland

Abstract: Eades and Wormald have shown that a bipartite graph drawn by the median heuristic has at most three times the number of edge crossing in the corresponding optimal drawing. In this paper we show that the bound of Eades and Wormald can be sharpened.

Keywords: bipartite graph, graph drawing, median heuristic, average heuristic, edge crossing

DOI: 10.3233/FI-1989-12408

Journal: Fundamenta Informaticae, vol. 12, no. 4, pp. 563-569, 1989

Received September 1988
|
Accepted January 1989
|
Published: 1 October 1989
Price: EUR 27.50
Show more