On drawing regular bipartite graphs

Abstract

This paper deals with heuristics for drawing bipartite graphs in the case the vertices to be ordered have a common degree. These graphs are called regular bipartite graphs. Our main result states that two completely different heuristics, the barycenter heuristic and the assignment heuristic, coincide on regular bipartite graphs.

Keywords:

• Regular bipartite graph
• graph drawing
• barycenter heuristic
• median heuristic
• assignment heuristic

C.R. Categories:

• F2.2
• g 2.2