In online dynamic graph drawing,constraints over nodes and node pairs help preserve a coherent mental map in a sequence of graphs.Defining the constraints is challenging due to the requirements of both preserving ment...In online dynamic graph drawing,constraints over nodes and node pairs help preserve a coherent mental map in a sequence of graphs.Defining the constraints is challenging due to the requirements of both preserving mental map and satisfying the visual aesthetics of a graph layout.Most existing algorithms basically depend on local changes but fail to do proper evaluations on the global propagation when setting constraints.To solve this problem,we introduce a heuristic model derived from PageRank which simulates the node movement as an inverse Markov process hence to give a global analysis of the layout's change,according to which different constraints can be set.These constraints,along with stress function,generate layouts maintaining spatial positions and shapes of relatively stable substructures between adjacent graphs.Experiments demonstrate that our method preserves both structure and position similarity to help users track graph changes visually.展开更多
Graph layout can help users explore graph data intuitively.However,when handling large graph data volumes,the high time complexity of the layout algorithm and the overlap of visual elements usually lead to a significa...Graph layout can help users explore graph data intuitively.However,when handling large graph data volumes,the high time complexity of the layout algorithm and the overlap of visual elements usually lead to a significant decrease in analysis efficiency and user experience.Increasing computing speed and improving visual quality of large graph layouts are two key approaches to solving these problems.Previous surveys are mainly conducted from the aspects of specific graph type,layout techniques and layout evaluation,while seldom concentrating on layout optimization.The paper reviews the recent works on the optimization of the visual and computational efficiency of graphs,and establishes a taxonomy according to the stage when these methods are implemented:pre-layout,in-layout and post-layout.The pre-layout methods focus on graph data compression techniques,which involve graphfiltering and graph aggregation.The in-layout approaches optimize the layout process from computing architecture and algorithms,where deep learning techniques are also included.Visual mapping and interactive layout adjustment are post-layout optimization techniques.Our survey reviews the current research on large graph layout optimization techniques in different stages of the layout design process,and presents possible research challenges and opportunities in the future.展开更多
基金supported by the National Key Research and Development Program of China under Grant No.2017YFB0701900the National Natural Science Foundation of China under Grant No.61100053the Key Laboratory of Machine Perception of Peking University under Grant No.K-2019-09.
文摘In online dynamic graph drawing,constraints over nodes and node pairs help preserve a coherent mental map in a sequence of graphs.Defining the constraints is challenging due to the requirements of both preserving mental map and satisfying the visual aesthetics of a graph layout.Most existing algorithms basically depend on local changes but fail to do proper evaluations on the global propagation when setting constraints.To solve this problem,we introduce a heuristic model derived from PageRank which simulates the node movement as an inverse Markov process hence to give a global analysis of the layout's change,according to which different constraints can be set.These constraints,along with stress function,generate layouts maintaining spatial positions and shapes of relatively stable substructures between adjacent graphs.Experiments demonstrate that our method preserves both structure and position similarity to help users track graph changes visually.
基金supported by National Natural Science Foundation of China(No.61872432).
文摘Graph layout can help users explore graph data intuitively.However,when handling large graph data volumes,the high time complexity of the layout algorithm and the overlap of visual elements usually lead to a significant decrease in analysis efficiency and user experience.Increasing computing speed and improving visual quality of large graph layouts are two key approaches to solving these problems.Previous surveys are mainly conducted from the aspects of specific graph type,layout techniques and layout evaluation,while seldom concentrating on layout optimization.The paper reviews the recent works on the optimization of the visual and computational efficiency of graphs,and establishes a taxonomy according to the stage when these methods are implemented:pre-layout,in-layout and post-layout.The pre-layout methods focus on graph data compression techniques,which involve graphfiltering and graph aggregation.The in-layout approaches optimize the layout process from computing architecture and algorithms,where deep learning techniques are also included.Visual mapping and interactive layout adjustment are post-layout optimization techniques.Our survey reviews the current research on large graph layout optimization techniques in different stages of the layout design process,and presents possible research challenges and opportunities in the future.
