More Related Content
More from Computer Science Club (20)
20140329 graph drawing_dainiak_lecture01
- 1. 亳亰舒仍亳亰舒亳 亞舒仂于 Computer Science 从仍弍, 仄舒 2014 仍亠从舒仆亟 舒亶仆磻, 个丐 个丐 www.dainiak.com
- 2. 亠亠于 亠仆亠舒仍仂亞亳亠从仂亠 亟亠亠于仂 亟亳仆舒亳亳 弌舒从仂仆仂于 (XII 于亠从)
- 3. 亠亠于 亠亠于仂 亟仂弍仂亟亠亠仍亠亶 (XIV 于亠从)
- 4. 亠亠于 亠亠于仂 亞亠仂于 (XIV 于亠从)
- 5. 亠亠于 仂仄亠亠仆仆亠 亟亠亠于 亳亰 舒亳 仍亳 (1857) 仂 亟亠亠于. A. Cayley. On the Theory of the Analytical Forms Called Trees. Philosophical Magazine, 4(13):172176, 1857.
- 6. 舒 仂亞亳亠从亳亶 从于舒亟舒 亟亳舒亞舒仄仄舒 仂仆仂亠仆亳亶 仄亠亢亟 亳仍仍仂亞亳亰仄舒仄亳. Juan de Celaya (14901558) (亅仂 亞舒 12.)
- 7. 舒 仍仍ﾑ舒亳 .-丐. 舒仆亟亠仄仂仆亟舒 (1771 亞.) 从 亰舒亟舒亠 仂弍 仂弍仂亟亠 舒仄舒仆仂亶 亟仂从亳 从仂仆仄.
- 8. 舒 仍仍ﾑ舒亳 丕. 舒仄亳仍仂仆舒 (1857) 从 亰舒亟舒亠 仂弍 仂弍仂亟亠 亳从仂舒亟舒.
- 9. 舒 舒 仄仂仍亠从仍 亳亰 舒亳 .. 舒仆舒 (1864).
- 10. 舒仆仆亳亠 舒亳 仗仂 于亳亰舒仍亳亰舒亳亳 H.W. Tutte 1963 How to draw a graph D. E. Knuth 1970 How shall we draw a tree
- 11. 弌亳仄仗仂亰亳仄 仗仂 Graph Drawing International Work Meeting on Graph Drawing, Marino (Rome), Italy, June 45, 1992 21st International Symposium on Graph Drawing, Bordeaux, France, September 2325, 2013 22nd International Symposium on Graph Drawing, W端rzburg, Germany, 24-26 September 2014
- 12. . 仆 仂 于亳亰舒仍亳亰舒亳亳 亞舒仂于 D.E. Knuth (GD' 1996): Graph drawing is the best possible field I can think of: It merges aesthetics, mathematical beauty and wonderful algorithms. It therefore provides a harmonic balance between the left and right brain parts. A good graph drawing algorithm should leave something for the users satisfaction.
- 13. 丐亳仗亳仆亠 仂弍仍舒亳 仗亳仄亠仆亠仆亳 亞舒仂于 Software engineering: UML 亟亳舒亞舒仄仄, 亟亳舒亞舒仄仄 于亰仂于仂于 亳仂仍仂亞亳: 亞亠仆仂仄亳从舒, 仗亳亠于亠 亠仗亳, 弌亠亳: 亳仆仄亠仆 仗舒于仍亠仆亳 亠礆亳, 仆亠仆亠 亠亰仂仗舒仆仂: 亠亠于亠 舒舒从亳 弌仂亳舒仍仆亠 亠亳: Twitter, Facebook, etc.
- 14. 仂仍亰仂于舒亠仍从亳亠 亠弍仂于舒仆亳 丼亳舒弍亠仍仆仂: 于亳亟仆 仂仆仂于仆亠 从仆亠 仂仂弍亠仆仆仂亳 亞舒舒. 仂仆仂仄亳亰仄: 亳仆仂从 亟仂仍亢亠仆 仂仂于亠于仂于舒 亳仍亠于仄 仂亞仍舒亠仆亳礆, 舒舒从亠仆仄 亟仍 从仂仆从亠仆仂亶 仗亳从仍舒亟仆仂亶 仂弍仍舒亳. 丕仗舒于仍磳仄仂: 仗仂仍亰仂于舒亠仍 仄仂亢亠 从仂仆仂仍亳仂于舒 仗舒舒仄亠 从仍舒亟从亳. 仂亟亠亶于亳亠 仂仂于亠于亠 亠仍亳 (亟亳仆舒仄亳亠从亳亶 亞舒 仆舒 从舒仆亠 / 于仂从仂从舒亠于亠仆仆舒 亟亳舒亞舒仄仄舒 亟仍 仗亠舒亳 / )
- 15. 弌仂亞仍舒亠仆亳 (conventions) 弌仂亞仍舒亠仆亳亠 仂 于仂亶于仂, 从仂仂仂仄 从仍舒亟从舒 亞舒舒 亟仂仍亢仆舒 亟仂于仍亠于仂 束弍亠仗亠从仂仍仂于仆仂損, 于 仗仂亳于仆仂仄 仍舒亠 亞舒 仆亠 亳舒亠 仍仂亢亠仆仆仄 于仂于亠. 亳仄亠: 亠亳仆 亞舒舒 仆亠 亟仂仍亢仆 仍亠亢舒 仆舒 弍舒, 从仂仆舒仄亳 从仂仂 仂仆亳 仆亠 磦仍ﾑ. 舒从 仄仂亞 亳亰仂弍舒亢舒 弍舒 (仂亠亰从仂仄 仗礆仂亶 / 仗仂仍亳仍亳仆亳亠亶 / 亟亞仂亶 仂从亢仆仂亳 / 仗仍舒亶仆仂仄 / ) 舒从 亟仂仍亢仆 舒仗仂仍舒亞舒 于亠亳仆 (亠仍亳 亠弍仂 亳亟 亳亰 于 , 仂 仍亠亢亳 仆亳亢亠 / 于亠亳仆 亳 亳亰亞亳弍 弍亠 亟仂仍亢仆 亳仄亠 亠仍仂亳仍亠仆仆亠 从仂仂亟亳仆舒 / ).
- 16. 弌仂亞仍舒亠仆亳 (conventions) 舒于亳仍仂 仂 仗仂亢亠仍舒仆亳亠, 从仂仂仂亠 仍亠亟亠 于仗仂仍仆亳 于 仄舒从亳仄舒仍仆仂 于仂亰仄仂亢仆仂仄 仂弍仄亠. 舒于亳仍舒 亳仄亠ﾑ, 于 仂仆仂于仆仂仄, 亠亳亠从 仄仂亳于舒亳. 亳仄亠: 亳于亠, 亳亰仂弍舒亢舒ﾑ亳亠 弍舒, 亟仂仍亢仆 弍 仗仂从仂仂亠. 仂仍亳亠于仂 亳亰亞亳弍仂于 仆舒 弍舒 亟仂仍亢仆仂 弍 仗仂仄亠仆亠. 丼亳仍仂 仗亠亠亠亠仆亳亶 弍亠 亟仂仍亢仆仂 弍 仗仂仄亠仆亠. 亠亳仆 仆亠 亟仂仍亢仆 仆舒仂亟亳 仍亳从仂仄 弍仍亳亰从仂. 丕亞仍 仄亠亢亟 仗亠亠亠从舒ﾑ亳仄亳 弍舒仄亳 仗仂弍仂仍亠. 仍仂舒亟 从仍舒亟从亳 仗仂仄亠仆亠. 弌亳仄仄亠亳亳 亞舒舒 亟仂仍亢仆 仗仂仍亠亢亳于舒.
- 17. 丼舒仂 仆亠 弍于舒亠 束仍亠亶損 从仍舒亟从亳
- 18. 丼亳舒弍亠仍仆仂 vs. 仂仂于亠于亳亠 仗舒于亳仍舒仄 There is a gap between the user's view and the formalism D. E. Knuth
- 19. 丐亟仆仂亳 于亳亰舒仍亳亰舒亳亳 亠舒仍仆 亞舒仂于 People don't want to draw graphs. They want to draw pictures that contain graphs. Brendan Madden, 2003 丕 亠舒仍仆仂亞仂 亞舒舒 亠 亠仄舒仆亳从舒 仗仂磦仍ﾑ 亠仄舒仆亳亠从亳亠 仗舒于亳仍舒.
- 20. 丐亟仆仂亳 于亳亰舒仍亳亰舒亳亳 亠舒仍仆 亞舒仂于 亳仄亠 亠仄舒仆亳亠从亳-仗仂亟亳从仂于舒仆仆 仗舒于亳仍: 亟亠仍亠仆仆亠 于亠亳仆 亟仂仍亢仆 舒仗仂仍舒亞舒 仆亠仗仂亟舒仍从. 亟亠仍亠仆仆亠 于亠亳仆 亟仂仍亢仆 舒仗仂仍舒亞舒 仆舒 仂亟仆仂亶 仗礆仂亶. 亟亠仍亠仆仆亠 于亠亳仆 亟仂仍亢仆 舒仗仂仍舒亞舒 于 亠仆亠 亳仆从舒. 亟亠仍亠仆仆亠 于亠亳仆 亟仂仍亢仆 舒仗仂仍舒亞舒 仆舒 仗亠亳亠亳亳.
- 21. 丕从仍舒亟从亳 弌弌 仍仂亢仆亠亠, 亠仄 从仍舒亟从舒 亞舒仂于: 仄仆仂亢亠于仂 亟仂仗仂仍仆亳亠仍仆 亠仆仂仍仂亞亳亠从亳 仗舒于亳仍.
- 22. 丕从仍舒亟从亳 弌弌 仍仂亢仆亠亠, 亠仄 从仍舒亟从舒 亞舒仂于: 仄仆仂亢亠于仂 亟仂仗仂仍仆亳亠仍仆 亠仆仂仍仂亞亳亠从亳 仗舒于亳仍.
- 23. 丐亠仆亳亠从亳亠 仗仂亟仂亟 从 于亳亰舒仍亳亰舒亳亳 丐仂仗仂仍仂亞亳 仂仄舒 仄亠亳从舒 亠仂亟, 仂仆仂于舒仆仆亠 仆舒 从仍舒亟从舒 仗仍舒仆舒仆 亞舒仂于 弌亳仍仂于亠 仄亠仂亟 亠仂亟 亳仗舒 束舒亰亟亠仍磺 亳 于仍舒于亶損
- 24. 丐仂仗仂仍仂亞亳 仂仄舒 仄亠亳从舒 亅舒仗 束仂仗仂仍仂亞亳晛: 仂仗亠亟亠仍磳仄, 从舒从 仗仂磲仂亠仆 弍舒 于仂从亞 从舒亢亟仂亶 于亠亳仆. 1,2,3,4,5 1,2 , 1,3 , 1,4 , 1,5 , 2,4 , 3,5 , 4,5
- 25. 丐仂仗仂仍仂亞亳 仂仄舒 仄亠亳从舒 亅舒仗 束仂仄舒損: 仂仗亠亟亠仍磳仄 仂仄 弍亠. ( 仍舒亠 仂仂亞仂仆舒仍仆 仗亠亟舒于仍亠仆亳亶 从仂仍亳亠于仂 亳亰仍仂仄仂于.)
- 26. 丐仂仗仂仍仂亞亳 仂仄舒 仄亠亳从舒 亅舒仗 束仄亠亳从舒損: 仗仂亟弍亳舒亠仄 于亠 亟仍亳仆.