《有田友和（桜美林大学）本桥友江（関东学院大）》由会员分享，可在线阅读，更多相关《有田友和（桜美林大学）本桥友江（関东学院大）（51页珍藏版）》请在金锄头文库上搜索。
1、An octal degree graph representation for the rectangular dissections,有田友和（桜美林大学）、本橋友江（関東学院大） 土田賢省（東洋大）、夜久竹夫（日大）年月日 日本大学文理学部,Title corrected,資料,IASTED SEA (Cambridge, 2002) HJ2003 (Hangary-Japan Sympos. Discrete Math., Tokyo) IASTED AI04 (Insbruck, 2004),対象 均一型矩形分割不均一型矩形分割操作（壁指向） 変形（壁移動、行列追加削除移動、） 特徴
2、抽出（表行合計計算、表構造正誤） 応用 図表（文書) 建物（OR) 地形図,1.Introduction Motivation Aim Known Representation Method Purpose,Motivation TablesHomogeneous Heterogeneous rectangular rectangulardissections dissectionEditing operations often cause unexpected results.,Word,MotivationExcel does not allow this operation,Aim Re
3、presentation method for rectangular dissection processing system. Formalization of rectangular dissection editing operations.,Known Representation Methods Quad-Tree Representation J.L.Bentley,1975 for Search Algorithm Rectangular Dual Graph Representation Kozminski,K and Kinnen,E,1984 for Plant Layo
4、ut,Known Representation Methods Quad-Tree Representation,NE,NW,SW,SE,NE,NW,SW,SE,Known Representation Methods Rectangular Dual Graph Representation,Horizontal edge Vertical edge,W,N,E,S,Known Representation MethodsExample 1 Quad-tree Rep. has a weak power of expression.,Known Representation MethodsE
5、xample 2 Rectangular Dual Graph Rep. may require higher complexity in editing operation.,Known results (cont.),Theorem. Decision problem of a graph to be a (homogeneous) grid graph O(n) (1990),Relate Results,Data Structures : Tessellation graphs (Motohashi et. al. FOSE02-Matsuyama) Viewer (Kirishima
6、 et. al., LA02Summer, IASTED SE 02-Cambridge-USA) Equivalent condition of graphs to be tessellation graphs (Kirishima et. al., IASTED AI 03-Insbruck),Purpose To propose a graph representation method for tables in consideration of editing and drawing and to investigate mathematical properties. To int
7、roduce typical algorithms on the graphs and evaluate their complexity. To introduce a graph grammar,2. Attribute Graphs for tables,Example,Def 2.1Table T (2,3)-table Partition P (1,1),(2,1),(1,2), . . . Grid g=(grow,gcolumn)north wall of c nw(c)=1, sw(c)=2, east wall of c ew(c)=6, ww(c)=2.,0,2,4,6,0
8、,2,1,cell,Def 2.2 Tabular Diagram D=(T,P,g)perimeter cells with width=0 or height=0 We consider tabular diagrams with perimeter cells.,0 0 2 4 6 6,0,0,1,2,2,Def 2.3 (Tessellation Graph) A tabular diagram D=(T,P,g) is represented by an attribute graph G=(V,E,L,A,)1st step put a node to a cellD G,Grap
9、h representation 2nd step set edges and edge labels nw(c) =nw(d)sw(c) =sw(d)ew(c) =ew(d)ww(c) =ww(d) D G,c,d,c,d,c,d,c,d,North wall edgeSouth Wall EdgeEast Wall EdgeWest Wall Edge,Graph representation 3rd step set an attributeD G,vc (1,2,6,2),nw(c)=1 sw(c)=2 ew(c)=6 ww(c)=2,c,2 6,1 2,d,vd,vc,d,c,Pro
10、perties D : a tabular diagram of an (n,m)-table GD : a tessellation graph for D. 1 node in GD corresponds to 1 cell in D The degree of a node in GD 8. Proposition 2.2 2|ED| = 6(2n-4) + 6(2m-4) + 8k + 16(k : the number of non perimeter cells),3D :rectangularpiped dissection : 24 degree quasi grid gra
11、phs,Horizontal 4 links (black) x nsew = 16 links Vertical 4 links (pink) x up-down 2 = 8 links Total 24 links,Similar results to Proposition 2.2 hold for the 16 degree quasi grid graphs ; degree 16 for the 24 quasi grid graphs ; degree 24.,Proposition 2.2 GD:a rectangular piped dissection graph for
12、D of an (m,n,l)-cube. k : the number of inner cells in GD. For #ED, 2x#ED = 20(n-2)(m-2)x2 + 20(m-2)(l-2)x2 + 20(l-2)(n-2)x2+ 16(n-2)x4 + 16(m-2)x4 + 16(l-2)x4+ 12 x 8+ 24k,Proposition (cf. Kundu)RD : A rectangular dissection with no wall crossing s.t. RD is not a T*-plan but is represented in a tes
13、sellation diagram,Proof. A spiral graph with perimeter cells and Its corresponding tessellation graphs,RemarkAttributes for location of inner cells : not necessary Location information cited in perimeter cells,3.1 ALGORITHM Unify-Cells (1) Input/Output Spec. Example,D,E,(2) Illustration of Unify-Cells MechanismGD GE (3) Theorem (Unify-Cells) Algorithm Unify-Cells runs in constant time.,3.2 ALGORITHM Move-East-Wall (1) INPUT/OUTPUT Spec. Example,D,E,Moved Wall,c,Input Output GD=(VD,ED,L,D,A,D) GE=(VE,EE,L,E,A,E) vc 0 : movement value,
