{"id":13057,"date":"2021-12-05T20:33:32","date_gmt":"2021-12-06T01:33:32","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=13057"},"modified":"2026-06-02T14:59:24","modified_gmt":"2026-06-02T18:59:24","slug":"tr-02-01-balanced-vertex-orderings-of-graphs","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2002\/tr-02-01-balanced-vertex-orderings-of-graphs\/","title":{"rendered":"TR-02-01: Balanced Vertex-Orderings of Graphs"},"content":{"rendered":"\n
\n
\n\n
\n
\n
\n

\n TR-02-01: Balanced Vertex-Orderings of Graphs\n <\/h1>\n \n \n <\/header>\n\n <\/div>\n\n <\/div>\n\n <\/div>\n<\/section>\n\n

Carleton University
\nTechnical Report<\/a> TR-02-01
\nMay 2002<\/p>\n\n\n\n

Balanced Vertex-Orderings of Graphs<\/h2>\n\n\n\n
\n
\n
\n
\n
\n
\n
\n
\n
Therese Biedl, Timothy Chan, Yashar Ganjali, MohammadTaghi Hajiaghayi, David R. Wood<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n
\n

Abstract<\/h3>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n\n\n\n

We consider the problem of determining a balanced ordering of the vertices of a graph; that is, the neighbors of each vertex are as evenly distributed to the left and right of as possible. This problem, which has applications in graph drawing for example, is shown to be NP-hard, and remains NP-hard for bipartite simple graphs with maximum degree six. We then describe and analyze a number of methods for determining a balanced vertex-ordering, obtaining optimal orderings for directed acyclic graphs and graphs with maximum degree three. Finally we consider the problem of determining a balanced vertex-ordering of a bipartite graph with a fixed ordering of one bipartition. When only the imbalances of the fixed vertices count, this problem is shown to be NP-hard. On the other hand, we describe an optimal linear time algorithm when the final imbalances of all vertices count. We obtain a linear time algorithm to compute an optimal vertex-ordering of a bipartite graph with one bipartition of constant size.<\/p>\n\n\n\n

TR-02-01.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"

Carleton University Technical Report TR-02-01 May 2002 Balanced Vertex-Orderings of Graphs Therese Biedl, Timothy Chan, Yashar Ganjali, MohammadTaghi Hajiaghayi, David R. Wood Abstract We consider the problem of determining a balanced ordering of the vertices of a graph; that is, the neighbors of each vertex are as evenly distributed to the left and right of […]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":12285,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"_cu_dining_location_slug":"","footnotes":"","_links_to":"","_links_to_target":""},"cu_page_type":[],"class_list":["post-13057","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":false},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13057","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/comments?post=13057"}],"version-history":[{"count":2,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13057\/revisions"}],"predecessor-version":[{"id":13059,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13057\/revisions\/13059"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12285"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=13057"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=13057"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}