An algorithm for embedding a biconnected planar graph to maximize the total sum of vertex- and edge-weights on the exterior window

0.00 Avg rating—0 Votes

Article ID:	iaor19921446
Country:	Japan
Volume:	J74-A
Issue:	7
Start Page Number:	1041
End Page Number:	1052
Publication Date:	Jul 1991
Journal:	Transactions of the Institute of Electronics, Information and Communication Engineers
Authors:	Kashiwabara Toshinobu, Masuda Sumio, Kotani Ken
Keywords:	combinatorial analysis, optimization

Abstract:

Let G=(V,E) be a biconnected planar graph whose vertices and edges have weights. This paper presents an O(ℝVℝ) time algorithm for finding a planar embedding of G such that the total sum of weights of the vertices and edges on its exterior window has the maximum value among all the planar embeddings of G. [In Japanese.]

Reviews

Required fields are marked *. Your email address will not be published.