词条 | Layered graph drawing |
释义 |
The ideal form for a layered drawing would be an upward planar drawing, in which all edges are oriented in a consistent direction and no pairs of edges cross. However, graphs often contain cycles, minimizing the number of inconsistently-oriented edges is NP-hard, and minimizing the number of crossings is also NP-hard, so layered graph drawing systems typically apply a sequence of heuristics that reduce these types of flaws in the drawing without guaranteeing to find a drawing with the minimum number of flaws. Layout algorithmThe construction of a layered graph drawing proceeds in a sequences of steps:
ImplementationsIn its simplest form, layered graph drawing algorithms may require O(mn) time in graphs with n vertices and m edges, because of the large number of dummy vertices that may be created. However, for some variants of the algorithm, it is possible to simulate the effect of the dummy vertices without actually constructing them explicitly, leading to a near-linear time implementation.[18] The "dot" tool in Graphviz produces layered drawings.[9] A layered graph drawing algorithm is also included in Microsoft Automatic Graph Layout[19] and in Tulip.[20] VariationsAlthough typically drawn with vertices in rows and edges proceeding from top to bottom, layered graph drawing algorithms may instead be drawn with vertices in columns and edges proceeding from left to right.[21] The same algorithmic framework has also been applied to radial layouts in which the graphs are arranged in concentric circles around some starting node[3][22] and to three-dimensional layered drawings of graphs.[3][23] In layered graph drawings with many long edges, edge clutter may be reduced by grouping sets of edges into bundles and routing them together through the same set of dummy vertices.[24] Similarly, for drawings with many edges crossing between pairs of consecutive layers, the edges in maximal bipartite subgraphs may be grouped into confluent bundles.[25] Drawings in which the vertices are arranged in layers may be constructed by algorithms that do not follow Sugiyama's framework. For instance, it is possible to tell whether an undirected graph has a drawing with at most k crossings, using h layers, in an amount of time that is polynomial for any fixed choice of k and h, using the fact that the graphs that have drawings of this type have bounded pathwidth.[26] For layered drawings of concept lattices, a hybrid approach combining Sugiyama's framework with additive methods (in which each vertex represents a set and the position of the vertex is a sum of vectors representing elements in the set) may be used. In this hybrid approach, the vertex permutation and coordinate assignment phases of the algorithm are replaced by a single phase in which the horizontal position of each vertex is chosen as a sum of scalars representing the elements for that vertex.[27] Layered graph drawing methods have also been used to provide an initial placement for force-directed graph drawing algorithms.[28] References1. ^1 2 3 4 5 6 7 8 9 {{citation | last1 = Di Battista | first1 = Giuseppe | last2 = Eades | first2 = Peter | author2-link = Peter Eades | last3 = Tamassia | first3 = Roberto | author3-link = Roberto Tamassia | last4 = Tollis | first4 = Ioannis G. | contribution = Layered Drawings of Digraphs | isbn = 978-0-13-301615-4 | pages = 265–302 | publisher = Prentice Hall | title = Graph Drawing: Algorithms for the Visualization of Graphs | year = 1998}}. 2. ^1 2 3 4 5 6 7 8 {{citation|contribution=Layered drawings of digraphs|first1=Oliver|last1=Bastert|first2=Christian|last2=Matuszewski|title=Drawing Graphs: Methods and Models|editor1-first=Michael|editor1-last=Kaufmann|editor2-first=Dorothea|editor2-last=Wagner|publisher=Springer-Verlag|series=Lecture Notes in Computer Science|volume=2025|year=2001|pages=87–120|doi=10.1007/3-540-44969-8_5|isbn=978-3-540-42062-0}}. 3. ^1 2 3 4 5 6 7 8 9 10 11 12 13 {{citation |contribution= Hierarchical Graph Drawing |first1=Patrick |last1=Healy |first2= Nikola S. |last2= Nikolov |pages= 409–453 |editor-first=Roberto |editor-last=Tamassia |editor-link=Roberto Tamassia |title= Handbook of Graph Drawing and Visualization |publisher=CRC Press |url= http://cs.brown.edu/~rt/gdhandbook/ |year=2014}}. 4. ^{{citation|first1=Kozo|last1=Sugiyama|first2=Shôjirô|last2=Tagawa|first3=Mitsuhiko|last3=Toda|title=Methods for visual understanding of hierarchical system structures|journal=IEEE Transactions on Systems, Man, and Cybernetics|volume=SMC-11|issue=2|pages=109–125|year=1981|mr=0611436|doi=10.1109/TSMC.1981.4308636}}. 5. ^{{citation|last1=Berger|first1=B.|author1-link= Bonnie Berger |last2=Shor|first2=P.|author2-link=Peter Shor|year=1990|contribution=Approximation algorithms for the maximum acyclic subgraph problem|title=Proceedings of the 1st ACM-SIAM Symposium on Discrete Algorithms (SODA’90)|pages=236–243|url=http://dl.acm.org/citation.cfm?id=320176.320203}}. 6. ^{{citation|last1=Eades|first1=P.|author1-link=Peter Eades|last2=Lin|first2=X.|last3=Smyth|first3=W. F.|year=1993|title=A fast and effective heuristic for the feedback arc set problem|journal=Information Processing Letters|volume=47|issue=6|pages=319–323|doi=10.1016/0020-0190(93)90079-O}}. 7. ^{{citation|last1=Eades|first1=P.|author1-link=Peter Eades|last2=Lin|first2=X.|year=1995|title=A new heuristic for the feedback arc set problem|journal=Australian Journal of Combinatorics|volume=12|pages=15–26}}. 8. ^{{citation|title=A fixed-parameter algorithm for the directed feedback vertex set problem|first1=Jianer|last1=Chen|first2=Yang|last2=Liu|first3=Songjian|last3=Lu|first4=Barry|last4=O'Sullivan|first5=Igor|last5=Razgon|journal=Journal of the ACM|volume=55|issue=5|pages=1|year=2008|doi=10.1145/1411509.1411511}}. 9. ^1 2 3 {{citation|title=A technique for drawing directed graphs|last1=Gansner|first1=E. R.|last2=Koutsofios|first2=E.|last3=North|first3=S. C.|last4=Vo|first4=K.-P.|journal=IEEE Transactions on Software Engineering|volume=19|issue=3|year=1993|pages=214–230|doi=10.1109/32.221135}}. 10. ^{{citation | last1 = Healy | first1 = Patrick | last2 = Nikolov | first2 = Nikola S. | contribution = How to layer a directed acyclic graph | doi = 10.1007/3-540-45848-4_2 | mr = 1962416 | pages = 16–30 | publisher = Springer-Verlag | series = Lecture Notes in Computer Science | title = Graph Drawing: 9th International Symposium, GD 2001 Vienna, Austria, September 23–26, 2001, Revised Papers | volume = 2265 | year = 2002| isbn = 978-3-540-43309-5 }}. 11. ^{{citation | last = Newbery | first = F. J. | contribution = Edge concentration: a method for clustering directed graphs | doi = 10.1145/72910.73350 | isbn = 0-89791-334-5 | pages = 76–85 | publisher = Association for Computing Machinery | title = Proceedings of the 2nd International Workshop on Software Configuration Management (SCM '89), Princeton, New Jersey, USA | year = 1989}}. 12. ^{{citation | last1 = Eppstein | first1 = David | author1-link = David Eppstein | last2 = Goodrich | first2 = Michael T. | author2-link = Michael T. Goodrich | last3 = Meng | first3 = Jeremy Yu | editor-last = Pach | editor-first = János | editor-link = János Pach | arxiv = cs.CG/0507051 | contribution = Confluent layered drawings | edition = 3383 | pages = 184–194 | publisher = Springer-Verlag | series = Lecture Notes in Computer Science | title = Proc. 12th Int. Symp. Graph Drawing (GD 2004) | year = 2004 | doi=10.1007/s00453-006-0159-8 | volume=47}}. 13. ^{{citation|title=Drawing graphs in two layers|first1=Peter|last1=Eades|author1-link=Peter Eades|first2=Sue|last2=Whitesides|author2-link=Sue Whitesides|journal=Theoretical Computer Science|volume=131|issue=2|year=1994|pages=361–374|doi=10.1016/0304-3975(94)90179-1}}. 14. ^1 {{citation|title=Edge crossings in drawings of bipartite graphs|first1=Peter|last1=Eades|author1-link=Peter Eades|first2=Nicholas C.|last2=Wormald|journal=Algorithmica|volume=11|issue=4|year=1994|pages=379–403|doi=10.1007/BF01187020}}. 15. ^{{citation|last=Mäkinen|first=E.|year=1990|title=Experiments on drawing 2-level hierarchical graphs|journal=International Journal of Computer and Mathematics|volume=36|pages=175–181|doi=10.1080/00207169008803921}}. 16. ^{{citation | last1 = Dujmović | first1 = Vida | last2 = Fernau | first2 = Henning | last3 = Kaufmann | first3 = Michael | doi = 10.1016/j.jda.2006.12.008 | issue = 2 | journal = Journal of Discrete Algorithms | mr = 2418986 | pages = 313–323 | title = Fixed parameter algorithms for one-sided crossing minimization revisited | volume = 6 | year = 2008}}. 17. ^{{citation | last1 = Brandes | first1 = Ulrik | last2 = Köpf | first2 = Boris | contribution = Fast and simple horizontal coordinate assignment | doi = 10.1007/3-540-45848-4_3 | location = Berlin | mr = 1962417 | pages = 31–44 | publisher = Springer | series = Lecture Notes in Comput. Sci. | title = Graph drawing (Vienna, 2001) | volume = 2265 | year = 2002| isbn = 978-3-540-43309-5 }}. 18. ^{{citation|contribution=An efficient implementation of Sugiyama’s algorithm for layered graph drawing|first1=Markus|last1=Eiglsperger|first2=Martin|last2=Siebenhaller|first3=Michael|last3=Kaufmann|title=Graph Drawing, 12th International Symposium, GD 2004, New York, NY, USA, September 29-October 2, 2004, Revised Selected Papers|series=Lecture Notes in Computer Science|publisher=Springer-Verlag|volume=3383|year=2005|pages=155–166|doi=10.1007/978-3-540-31843-9_17|isbn=978-3-540-24528-5}}. 19. ^{{citation | last1 = Nachmanson | first1 = Lev | last2 = Robertson | first2 = George | last3 = Lee | first3 = Bongshin | editor1-last = Hong | editor1-first = Seok-Hee | editor2-last = Nishizeki | editor2-first = Takao | editor2-link = Takao Nishizeki | editor3-last = Quan | editor3-first = Wu | contribution = Drawing Graphs with GLEE | doi = 10.1007/978-3-540-77537-9_38 | pages = 389–394 | publisher = Springer-Verlag | series = Lecture Notes in Computer Science | title = Graph Drawing, 15th International Symposium, GD 2007, Sydney, Australia, September 24–26, 2007, Revised Papers | contribution-url = ftp://ftp.research.microsoft.com/pub/TR/TR-2007-72.pdf | volume = 4875 | year = 2008| isbn = 978-3-540-77536-2 }}. 20. ^{{citation | last = Auber | first = David | editor1-last = Jünger | editor1-first = Michael | editor2-last = Mutzel | editor2-first = Petra | editor2-link = Petra Mutzel | contribution = Tulip – A Huge Graph Visualization Framework | isbn = 978-3-540-00881-1 | publisher = Springer-Verlag | title = Graph Drawing Software | year = 2004}}. 21. ^{{citation|contribution=Some modifications of Sugiyama approach|first=Danil E.|last=Baburin|title=Graph Drawing, 10th International Symposium, GD 2002, Irvine, CA, USA, August 26–28, 2002, Revised Papers|publisher=Springer-Verlag|series=Lecture Notes in Computer Science|year=2002|volume=2528|pages=366–367|doi=10.1007/3-540-36151-0_36|isbn=978-3-540-00158-4}}. 22. ^{{citation|title=A radial adaptation of the Sugiyama framework for visualizing hierarchical information|first=Christian|last=Bachmaier|journal=IEEE Transactions on Visualization and Computer Graphics|volume=13|issue=3|year=2007|pages=583–594|doi=10.1109/TVCG.2007.1000|pmid=17356223}}. 23. ^{{citation|contribution=Layered drawings of directed graphs in three dimensions|first1= Seok-Hee|last1= Hong|first2= Nikola S. |last2=Nikolov|title=Proceedings of the 2005 Asia-Pacific Symposium on Information Visualisation (APVis '05)|series=Conferences in Research and Practice in Information Technology|volume=45|year=2005|pages=69–74|url=http://dl.acm.org/citation.cfm?id=1082326}}. 24. ^{{citation|contribution=Improving layered graph layouts with edge bundling|first1=Sergey |last1=Pupyrev|first2= Lev|last2= Nachmanson |first3= Michael |last3=Kaufmann|publisher=Springer-Verlag|series=Lecture Notes in Computer Science|title=Graph Drawing, 18th International Symposium, GD 2010, Konstanz, Germany, September 21-24, 2010, Revised Selected Papers|volume=6502|year=2011|pages=329–340|doi=10.1007/978-3-642-18469-7_30|isbn=978-3-642-18468-0 }}. 25. ^{{citation|title=Confluent layered drawings|first1=David|last1=Eppstein|author1-link=David Eppstein|first2=Michael T.|last2=Goodrich|author2-link=Michael T. Goodrich|first3=Jeremy Yu|last3=Meng|journal=Algorithmica|volume=47|issue=4|year=2007|pages=439–452|doi=10.1007/s00453-006-0159-8|arxiv=cs/0507051}}. 26. ^{{citation | last1 = Dujmović | first1 = V. | last2 = Fellows | first2 = M.R. | last3 = Kitching | first3 = M. | last4 = Liotta | first4 = G. | last5 = McCartin | first5 = C. | last6 = Nishimura | first6 = N. | last7 = Ragde | first7 = P. | last8 = Rosamond | first8 = F. | last9 = Whitesides | first9 = S. | doi = 10.1007/s00453-007-9151-1 | issue = 2 | journal = Algorithmica | pages = 267–292 | title = On the parameterized complexity of layered graph drawing | volume = 52 | year = 2008}}. 27. ^{{citation|contribution=Automated layout of concept lattices using layered diagrams and additive diagrams|first=Richard|last=Cole|title=Proceedings of the 24th Australasian Conference on Computer Science (ACSC '01)|year=2001|pages=47–53|url=http://dl.acm.org/citation.cfm?id=545570}}. 28. ^{{cite journal| url=http://www.nature.com/nbt/journal/v18/n12/full/nbt1200_1257.html | volume=18|author1=Benno Schwikowski|author2=Peter Uetz|author3=Stanley Fields|last-author-amp=yes|journal=Nature Biotechnology| title=A network of protein−protein interactions in yeast|year=2000|pmid=11101803| pages=1257–1261| doi=10.1038/82360| issue=12}} 1 : Graph drawing |
随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。