00000ctm a22000004a 4500 UP-99796217610396023 Buklod 20120706110406.0 m |o d | ta 120706s2010 xx d r |||| u| (iLib)UPD-00187104197 DML eng DMLUC LG 995 2010 C65 S9 Sy, Natalie W. On the octagonal drawings of a class of 2-4 plane graphs with bends and with prescribed face areas by Natalie W. Sy. 2010. vii, 53 leaves ill. "March 2010." Thesis (M.S. Computer Science)--University of the Philippines Diliman. In this thesis, we let S be the class of all good slicing 2-4 plane graphs having an inner vertex of degree 4. We construct an algorithm to show that any graph in S with prescribed face areas has an octagonal drawing with bends and with prescribed face areas. Roughly speaking, by an octagonal drawing, we mean an orthogonal drawing wherein its outer facial cycle is drawn in a rectangular shape and each inner face is drawn in a shape of a rectilinear polygon containing not more than 8 polygonal vertices. By a slicing graph, we mean a plane graph which is said to be good, if one of the two subrectangles (upper and lower) obtained by embedding any horizontal slice will not be sliced vertically. Moreover, when a good slicing tree is given, we show that an octagonal drawing can be determined in linear time. Our algorithm is a modification of the one given by Rahman, Miura, and Nishizeki [5] which also finds an octagonal drawing of any good slicing 2-3 plane graph. Graph algorithms. FI UP Thesis UPD DARCHIVES LG 995 2010 C65 S9 Thesis