On the octagonal drawings of a class of 2-4 plane graphs with bends and with prescribed face areas - Sy, Natalie W. (2010)
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.