检索结果-内蒙古大学图书馆

32nd international symposium on graph drawing and network visualization, gd 2024

作者： Chaplick, Steven Förster, Henry Hoffmann, Michael Kaufmann, Michael Maastricht University Netherlands Universität Tübingen Germany Department of Computer Science ETH Zürich Switzerland

ISBN: (纸本)9783959773430

We show that every planar graph has a monotone topological 2-page book embedding where at most (4n - 10)/5 (of potentially 3n - 6) edges cross the spine, and every edge crosses the spine at most once;such an edge is called a biarc. We can also guarantee that all edges that cross the spine cross it in the same direction (e.g., from bottom to top). For planar 3-trees we can further improve the bound to (3n - 9)/4, and for so-called Kleetopes we obtain a bound of at most (n - 8)/3 edges that cross the spine. the bound for Kleetopes is tight, even if the drawing is not required to be monotone. A Kleetope is a plane triangulation that is derived from another plane triangulation T by inserting a new vertex vf into each face f of T and then connecting vf to the three vertices of f. © Steven Chaplick, Henry Förster, Michael Hoffmann, and Michael Kaufmann.

关键词： graph embeddings

来源：评论

学校读者我要写书评

暂无评论

Pole Dancing: 3D Morphs for Tree drawings 26th

Pole Dancing: 3D Morphs for Tree Drawings

引用

26th international symposium on graph drawing and network visualization (gd)

作者： Arseneva, Elena Bose, Prosenjit Cano, Pilar D'Angelo, Anthony Dujmovic, Vida Frati, Fabrizio Langerman, Stefan Tappini, Alessandra St Petersburg State Univ SPbU St Petersburg Russia Carleton Univ Ottawa ON Canada Univ Politecn Cataluna Barcelona Spain Univ Ottawa Ottawa ON Canada Roma Tre Univ Rome Italy Univ Libre Bruxelles ULB Brussels Belgium Univ Perugia Perugia Italy

ISBN: (纸本)9783030044145;9783030044138

We study the question whether a crossing-free 3D morph between two straight-line drawings of an n-vertex tree can be constructed consisting of a small number of linear morphing steps. We look both at the case in which the two given drawings are two-dimensional and at the one in which they are three-dimensional. In the former setting we prove that a crossing-free 3D morph always exists with O(log n) steps, while for the latter circle minus(n) steps are always sufficient and sometimes necessary.

关键词： visualization

来源：评论

学校读者我要写书评

暂无评论

Arrangements of pseudocircles: Triangles and drawings 25th

引用

25th international symposium on graph drawing and network visualization, gd 2017

作者： Felsner, Stefan Scheucher, Manfred Technische Universität Berlin Berlin Germany Graz University of Technology Graz Austria

ISBN: (纸本)9783319739144

A pseudocircle is a simple closed curve on the sphere or in the plane. the study of arrangements of pseudocircles was initiated by Grünbaum, who defined them as collections of simple closed curves that pairwise intersect in exactly two crossings. Grünbaum conjectured that the number of triangular cells p3 in digon-free arrangements of n pairwise intersecting pseudocircles is at least 2n - 4 We present examples to disprove this conjecture. With a recursive construction based on an example with 12 pseudocircles and 16 triangles we obtain a family with p3(A)/n → 16/11 = 1.45. We expect that the lower bound p3(A) ≥ 4n/3 is tight for infinitely many simple arrangements. It may however be that digon-free arrangements of n pairwise intersecting circles indeed have at least 2n - 4 triangles. For pairwise intersecting arrangements with digons we have a lower bound of p3 ≥ 2n/3, and conjecture that p3 ≥ n - 1. Concerning the maximum number of triangles in pairwise intersecting arrangements of pseudocircles, we show that p3 ≤ 2n2/3+O(n). this is essentially best possible because families of pairwise intersecting arrangements of n pseudocircles with p3/n2 → 2/3 as n→∞ are known. the paper contains many drawings of arrangements of pseudocircles and a good fraction of these drawings was produced automatically from the combinatorial data produced by the generation algorithm. In the final section we describe some aspects of the drawing algorithm. © Springer international Publishing AG 2018.

关键词： drawing (graphics)

来源：评论

学校读者我要写书评

暂无评论

On vertex- and empty-ply proximity drawings 25th

引用

25th international symposium on graph drawing and network visualization, gd 2017

作者： Angelini, Patrizio Chaplick, Steven De Luca, Felice Fiala, Jiří Hančl, Jaroslav Heinsohn, Niklas Kaufmann, Michael Kobourov, Stephen Kratochvíl, Jan Valtr, Pavel Wilhelm-Schickhard-Institut für Informatik Universität Tübingen Tübingen Germany Lehrstuhl für Informatik I Universität Würzburg Würzburg Germany Università degli Studi di Perugia Perugia Italy Prague Czech Republic Department of Computer Science University of Arizona Tucson United States

ISBN: (纸本)9783319739144

We initiate the study of the vertex-ply of straight-line drawings, as a relaxation of the recently introduced ply number. Consider the disks centered at each vertex with radius equal to half the length of the longest edge incident to the vertex. the vertex-ply of a drawing is determined by the vertex covered by the maximum number of disks. the main motivation for considering this relaxation is to relate the concept of ply to proximity drawings. In fact, if we interpret the set of disks as proximity regions, a drawing with vertex-ply number 1 can be seen as a weak proximity drawing, which we call empty-ply drawing. We show non-trivial relationships between the ply number and the vertex-ply number. then, we focus on empty-ply drawings, proving some properties and studying what classes of graphs admit such drawings. Finally, we prove a lower bound on the ply and the vertex-ply of planar drawings. © Springer international Publishing AG 2018.

关键词： drawing (graphics)

来源：评论

学校读者我要写书评

暂无评论

Storyline visualizations with Ubiquitous Actors 28th

Storyline Visualizations with Ubiquitous Actors

引用

28th international symposium on graph drawing and network visualization, gd 2020

作者： Di Giacomo, Emilio Didimo, Walter Liotta, Giuseppe Montecchiani, Fabrizio Tappini, Alessandra Engineering Department University of Perugia Perugia Italy

ISBN: (纸本)9783030687656

Storyline visualizations depict the temporal dynamics of social interactions, as they describe how groups of actors (individuals or organizations) change over time. A common constraint in storyline visualizations is that an actor cannot belong to two different groups at the same time instant. However, this constraint may be too severe in some application scenarios, thus we generalize the model by allowing an actor to simultaneously belong to distinct groups at any point in time. We call this model Storyline with Ubiquitous Actors (SUA). Essential to our model is that an actor is represented as a tree rather than a single line. We describe an algorithmic pipeline to compute storyline visualizations in the SUA model and discuss case studies on publication data. © 2020, Springer Nature Switzerland AG.

关键词： visualization

来源：评论

学校读者我要写书评

暂无评论

the crossing number of the cone of a graph

The crossing number of the cone of a graph

引用

作者： Alfaro, Carlos A. Arroyo, Alan Derňár, Marek Mohar, Bojan Banco de México Ciudad de México Mexico Department of Combinatorics and Optimization University of Waterloo OntarioN2L 3G1 Canada Faculty of Informatics Masaryk University Brno Czech Republic Department of Mathematics Simon Fraser University BurnabyBCV5A 1S6 Canada IMFM Department of Mathematics Ljubljana Slovenia

Motivated by a problem asked by Richter and by the long standing Harary-Hill conjecture, we study the relation between the crossing number of a graph G and the crossing number of its cone CG, the graph obtained from G by adding a new vertex adjacent to all the vertices in G. Simple examples show that the difference cr(CG) − cr(G) can be arbitrarily large for any fixed k = cr(G). In this work, we are interested in finding the smallest possible difference;that is, for each nonnegative integer k, find the smallest f(k) for which there exists a graph with crossing number at least k and cone with crossing number f(k). For small values of k, we give exact values of f(k) when the problem is restricted to simple graphs and show that f(k) = k + Θ(k) when multiple edges are allowed. © 2018 Society for Industrial and Applied Mathematics.

关键词： graph theory

来源：评论

学校读者我要写书评

暂无评论

Block crossings in storyline visualizations

引用

Journal of graph Algorithms and Applications 2017年第5期21卷 873-913页

作者： Van Dijk, thomas C. Fink, Martin Fischer, Norbert Lipp, Fabian Markfelder, Peter Ravsky, Alexander Suri, Subhash Wolff, Alexander Lehrstuhl für Informatik I Universität Würzburg Germany University of California Santa Barbara United States Pidstryhach Institute for Applied Problems of Mechanics and Mathematics National Academy of Sciences of Ukraine Lviv Ukraine

Storyline visualizations help visualize encounters of the characters in a story over time. Each character is represented by an x-monotone curve that goes from left to right visualizing progression of time. A meeting is represented by having the characters that participate in the meeting run close together for some time. In order to keep the visual complexity low, rather than just minimizing pairwise crossings of curves, we propose to count block crossings, that is, pairs of intersecting bundles of lines. In a block crossing, two blocks of parallel lines intersect each other, which is less distracting than the same number of individual crossings being spread over the drawing. In this paper, we show that minimizing the number of block crossings is NP-hard, even if all meetings are of size 2. For this special case, we present a greedy heuristic, which we evaluate experimentally. We show that the general case is fixed-parameter tractable. Our main results is a constant-factor approximation algorithm for meetings of bounded size. the algorithm is based on (approximately) solving a hyperedge deletion problem on hypergraphs that may be of independent interest. © 2017, Brown University. All rights reserved.

关键词： visualization

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：