BoxRectangular Drawing Department of Ination and 信息框矩形盒拉深部

1、box-rectangular drawingrida sadekoverviewnsome definitions and observationsnproblem: finding a box-rectangular drawing of a graph g qspecific case:ngiven 4 vertices corresponding to corner boxesnlinear time algorithmqgeneral case:nno given verticesnlinear time algorithmnote: for simplicity we are go

2、ing to assume that g has 3 or more vertices and is 2-connected.who established these results?nrahman et al. established: qa necessary and sufficient condition for the existence of a box-rectangular drawing of a plane graph, andqa linear time algorithm to find it if it exists.definitions and observat

3、ions:nmultigraph is a graph which may have edges sharing both ends.nin a brd, a vertex may be drawn as a degenerate box.na degenerate box is called a point and a non-degenerate box is called a real box. nc0(g) is the outer rectangle which has exactly 4 corners.na box d is called a corner box if it c

4、ontains at least one corner. it can be degenerate. factsnany box-rectangular drawing has either two, three or 4 corner boxes. facts (2)nany corner box contains either one or two corners.nin a box-rectangular drawing d of g, any vertex of degree two or three satisfies one of the following: i.vertex v

5、 is drawn as a point containing no corner;ii.v is drawn as a corner box containing exactly one corner; oriii.v is drawn as a corner real box containing exactly two corners.vfacts (3)nin any box-rectangular drawing d of g, every vertex of degree five or more is drawn as a real box.lemmanif g has a bo

6、x-rectangular drawing, then g has a box rectangular drawing in which every vertex of degree four or more is drawn as a real box.proof of lemmaa)assume g has a box rectangular drawing, then by the last fact we know that every vertex of degree five or more in g must be drawn as a real box.b)if a verte

7、x v, where d(v) = 4, is drawn as a point in d then modify the drawing d such that v is drawn as follows: illustration of proof:finding brd if it exists: 4 designated verticesntwo major operations: 1.removal of a vertex of degree two: qlet v be a vertex where d(v)=2, qwe replace the 2 edges u1v and u

8、2v incident to v with a single edge u1u2,qand we delete v.2.replacement of a vertex by a cycle: brd with designated vertices (contd.)nidea: construct g from g using g as intermediate. then make a brd for g.qconstruct g by removing all non-designated vertices of degree two one by one from g nall vert

9、ices of degree 2 in g will be designated vertices nthey must be drawn as corner points in any brd of g. nevery designated vertex of degree 3 in g must be drawn as a real box since it is a corner.nevery non designated vertex of degree 3 in g must be drawn as a point. result: using the last lemma (pro

10、ved earlier), this implies that:if g has a brd then g has a brd d where all designated vertices of degree 3 and all vertices of degree 4 or more in g are drawn as real boxes.brd with designated vertices (contd.)qconstruct g from g:nreplace by a cycle each of the designated vertices of degree 3 and t

11、he vertices of degree four or more. nthe replaced cycle corresponding to a designated vertex x of degree 3 or more contains exactly one outer edge ex where x is one of the designated vertices. nput a dummy vertex x of degree 2 on ex. result: g is a simple graph and has exactly four outer vertices a,

12、 b, c and d of degree 2 and all other vertices are of degree 3. brd with designated vertices (contd.)brd with designated vertices (contd.)ntheorem:let g be a plane graph with four designated outer vertices a,b,c and d,and let g be the graph transformed from g as mentioned before.then, g has a brd wi

13、th corner boxes a,b,c, and d if and only if g has brd with designated corners a,b,c, and d. nproof:qthe necessity: (trivial)from the way g is constructed, if g has a brd then g will have one. qthe sufficiency: assume that g has a brd. nin d, each replaced cycle is drawn as a rectangle since it is a

14、face in d. plus, the 4 outer vertices a,b,c and d of degree 2 in g are drawn as the corners of the rectangle corresponding to c0(g) d immediately gives d having the 4 vertices a,b,c and d as corner boxes. ninsert the non-designated vertices of degree 2 on horizontal or vertical line segments in d,th

15、en we obtain the brd of g having a,b,c, and d as corner boxes. time complexitynconstructing g from g takes linear time.qremoving vertices of degree 2 takes o(n). neach replacement takes constant time, andnthere is at most a linear number of vertices to be replaced. qreplacing the vertices, that need

16、 to be replaced, by a cycle takes o(n)nthe replacement of a vertex takes o(d) where d is the degree of the vertex. nbut the sum of the degrees of the vertices is twice the number of edges since each edge contribute one degree to each vertex at its ends o(n) overall.grid sizenthe half perimeter of th

17、e brd d of g is bounded by m+2.qlet n2 be the non-designated vertices of degree 2 in g.qlet n = |v(g)| and m = |e(g)| m = m n2 (because we remove 2 edges and add one for each of the n2 vertices).qwe replace some vertices in g by cycles and add at most 4 dummy vertices to construct g g has at most 2m

18、 + 4 vertices.grid size (contd)nby theorem 6.3.8 which states that if all vertices of a plane graph g have degree 3 except the 4 corners, then the sizes of any compact rectangular grid drawing d of g satisfy w + h = n/2. qin our case, the half perimeter (w+h) of the produced rectangular drawing d is

19、 bounded then by:(2m + 4)/2 = m + 2qthe insertion of each of the n2 vertices of degree 2 back to get d increases the half perimeter at most by one half perimeter of d is bounded by:m + 2 + n2 = m + 2finding brd if it exists: problem recallncase 1: (solved)a set of outer vertices of a plane graph g a

20、re designated as corner boxesncase 2: the general case (to be solved)no designated vertices in advanceqproblem definition:nsee whether g has some set of outer vertices such that there is a brd of g having them as the corner boxes.nhow to find if they exist.brd without designated corners (contd)nfirs

21、t, we will derive a necessary and sufficient condition for a plane graph g with maximum degree 3 to have a brd and give a linear time algorithm to find it.nsecond, we reduce brd problem of a plane graph with 4 to that of a new plane graph j with 3. brd without designated corners (contd)nmain result:

22、 a plane graph g with 3 has a brd (for some set of outer vertices designated as corner boxes) if and only if g satisfies the following 2 conditions:i.every 2-legged or 3-legged cycle in g contains an outer edge; andii.2c2 + c3 4 for any independent set of cycles in g, where c2 and c3 are the numbers

23、 of 2-legged and 3-legged cycles respectively.factnin a box-rectangular drawing d of g, qany 2-legged cycle contains at least two corners of the outer rectangle, qany 3-legged cycle of g contains at least one corner, andqany cycle with four or more legs may contain no corner.necessity of the main re

24、sult theoremnfirst condition: assume that g has a brd. qby the previous fact, nany 2-legged or 3-legged cycle contains a corner of the outer rectangle contains an outer edge.nsecond condition: let s be any independent set of cycles in g. qby the previous fact, neach of the c2 2-legged cycles in s co

25、ntains at least 2 corners, and neach of the c3 3-legged cycles in s contains at least one corner.qsince the cycles in s are independent (vertex-disjoint with each other) this means there are at least 2c2 + c3 corners of the outer rectangleqthe outer rectangle has exactly four corners 2c2 + c3 4suffi

26、ciency of the main result theoremnthe proof for the sufficiency is a constructive proofnthe proof leads to a linear time algorithm to find a brd if it exists.important definitionncubic graphs: they are connected graphs having the property that each node has degree exactly 3.sufficiency of the main r

27、esult theorem (contd)nlemma (will not proof it here): qlet g be a plane graph with 3. qassume g satisfies the condition of the main result, and that g has at most 3 outer vertices of degree 3.qthen g has a box-rectangular drawing. sufficiency of the main result theorem (contd)nby the previous lemma,

28、 we may assume that g has 4 or more outer vertices of degree 3 we can choose 4 distinct outer vertices of degree 3 as corner boxes. nno vertex v of degree 2 is chosen as corner box, the edges incident to v are drawn on a common straight line segment in a brd of g. nso, let g be the cubic graph obtai

29、ned from g by removing all vertices of degree 2 one by one. we can construct d from d. sufficiency of the main result theorem (contd)nlemma: qlet g be a plane cubic graph. qassume that g satisfies: ncondition (i) from the main result (every 2-legged and 3 legged cycles contain an outer edge); andng

30、has four or more outer vertices; andnthere is exactly one c0(g)-component (a c0(g)-component is a subgraph j of g that consists of a single inner edge joining 2 outer vertices).qthen a)g has a 3-legged cycle, andb)if g has 2 or more independent 3-legged cycles, then the set of all minimal 3-legged c

31、ycles in g is independent (a k-legged cycle is minimal if g(c) does not contain any other k-legged cycle of g).sufficiency of the main result theorem (contd)nproof of part (a)qlet w be any outer vertex, andqlet e be the inner edge incident to w. qlet x be the other end of e then x is an inner vertex

32、 since g has one c0(g)-component and 4 or more outer vertices. qe belongs to exactly 2 faces say f1 and f2. qsince g has one c0(g)-component and since g is a cubic graph then: the contour of f1 contains 2 outer vertices: w and another say y. the same goes for f2. it has w and say z.qy z since d(y) =

33、 d(z) = 3.q g has a 3-legged cycle c with leg-vertices x, y and z.note: the legs of this 3-legged cycle meet at common vertex w.sufficiency of the main result theorem (contd)nproof sketch of part (b)qassume for contradiction that g has 2 or more 3-legged cycles but 2 minimal 3-legged cycles c and c

34、are not independent g(c) and g(c) share a common vertex (let e1.3 and e1.3 be the legs of c and c respectively).qclaim that g(c) and g(c) do not share a common face.qsuppose for contradiction that g(c) and g(c) do share a common face. get the conclusion that g does not have 2 or more independent 3-l

35、egged cycles contradictionqand then use this with the fact that g is cubic and observe that g(c) and g(c) share a common edge on c and c. to contradict with the first assumption by arriving to the conclusion that g has exactly 3 outer vertices contradiction.sufficiency of the main result theorem (co

36、ntd)nnow, we can prove the following lemma:qlet g be a planar cubic graph. qassume that g satisfies the 2 conditions of the main result and that g has four or more outer vertices. qthen g has a box-rectangular drawing.sufficiency of the main result theorem (contd)nfirst lets observe that:if g has a

37、2-legged cycle c,then g has a pair of independent 2-legged cycles.qby condition (i):c contains an outer edge the 2 legs of c are outer edges, say (v, v) and (w, w).nlet v and w be the leg vertices of c. nit is trivial to say that v wn g has a 2-legged cycle c which has v and w as leg vertices and c

38、and c are independent. sufficiency of the main result theorem (contd)nso, we will consider 2 cases: qcase 1: g has no 2-legged cycle.qcase 2: g has a pair of independent 2-legged cycles. case 1: g has no 2-legged cycles.nthis case means that g has one c0(g)-component, otherwise g would have a 2-legg

39、ed cycle. n by the previous lemma, g has a 3-legged cycle. case 1: g has no 2-legged cycles (contd)nchoose the 4 corner boxes as follows:q2 cases: a)g has no pair of independent 3-legged cyclesb)g has a pair of independent 3-legged cyclescase 1: g has no 2-legged cycles: sub-case (a)nchoose 4 outer

40、vertices arbitrarily and regard them as the 4 designated vertices for a brd of g. nclaim: every 3-legged cycle c in g has at least one designated vertex.qsince c has an outer edge by condition (i) of the main result exactly 2 of the 3 legs of c are outer edges. say x and y are the leg vertices of th

41、ese 2 legs.case 1: g has no 2-legged cycles: sub-case (a)(cntd.)nlet p be the path from x to y on c0(g). then p has exactly one intermediate vertex z: otherwise either g would have more than one c0(g)-component or a pair of independent 3-legged cycles contradiction. (remember the note proof (a) of l

42、emma on slide 28 where we said that these 3 legs meet at one point w and this point is exactly the vertex z we are mentioning).n we can know that all 3 legs are incident to z n all outer vertices except z lie on c.n c contains at least one of the four designated vertices (whether z is one of them or

43、 not) n claim is proven.case 1: g has no 2-legged cycles: sub-case (b)ng has a pair of independent 3-legged cycles. nlet m be the set of all minimal 3-legged cycles in g. nby the previous lemma (slide 28), m is independent. nlet k = |m|, then k 4 by condition (ii) of main result (2c2+c34) that this

44、theorem satisfies. nfor each 3-legged cycle cj; where 1 j 4; in m,we arbitrarily choose an outer vertex on cj. if k4 we arbitrarily chose 4-k outer vertices which are not chosen so far.n we have chosen exactly four outer vertices, and we take these vertices to be the 4 designated vertices of a brd o

45、f g.illustrationnvertices a, b, c and d are chosen as the designated vertices. na, b and d are chosen on 3 independent 3-legged cycles and vertex c is chosen arbitrarily on c0(g). illustration (cntd.)nclaim: every 3-legged cycle c of g has at least one designated vertex:qc has a designated vertex if

46、 c is minimal (since c belongs to m and this is how we chose the designated vertices). qif c is not minimal then g(c) contains a minimal 3-legged cycle cj that belongs to m and that cj has a designated outer vertex.qso we have chosen 4 designated outer verticesconstructionnreplace each designated ve

47、rtex by a cycle and add a dummy vertex of degree 2 on the edge of the cycle that belongs to the outer cycle.nthe new graph is g where all vertices have degree 3 except the 4 dummy outer vertices.nfrom chapter 6 there is a theorem that says: qassume that g is a 2-connected plane graph with 3, and 4 o

48、uter vertices of degree 2 are designated as the corners, then g has a rectangular drawing if and only if nany 2-legged cycle contains 2 or more corners, andnany 3-legged cycle contains one or more cornersconstruction (contd)ng satisfies the conditions of that theorem and we can draw a rectangular drawing d as shown in the figure.nreplace the four fac