课题基金 / 基金详情

Visibility Representations with Crossings

Visibility Representations with Crossings
具有交叉口的可见性表示
批准号:
239775286
负责人:
Professor Dr. Franz Josef Brandenburg
金额:
$0.0万
依托单位:
依托单位国家:
德国
项目类别:
Research Grants
财政年份:
2013
资助国家:
德国
项目状态:
已结题
起止时间:
2012-12-31 至 2015-12-31

项目摘要

项目成果

Professor Dr. Franz Josef Brandenburg的其他基金

相似基金

相关文献

中文摘要
翻译
图是建立离散结构模型的重要工具。它们也称为网络、计划、图表或模式。图的广泛使用是基于有图的事实。平面图是最著名和研究最多的一类图。然而,大多数图形都是非平面的,特别是在应用程序中。最近,这导致了超平面图形的引入。这样的图以某种规则的方式具有交叉点,并且它们采用了平面图的重要性质,例如线性边数和绘制算法。平面图通常画成直线。有具有水平和垂直线段以及可见性表示的正交图,其中顶点由水平线表示,边由各自顶点之间的垂直可见性表示。可见性表示不像直线图形那么常见,但它们在算法上更容易,在概念上也更灵活。如果允许以某种受控的方式穿越,那么能见度表示背后有一种未被探索的潜力。然后,可见性表示法将主导常规绘图样式。它们提供了许多选项来定义超平面图形。在这个项目中,我们希望探索可见性表示的这种潜力。特别地,我们定义了一类新的超平面图,并研究了典型的图论性质和识别问题的复杂性。此外,我们还将开发优化的图形绘制算法。我们的研究将有助于发展超越平面性。
英文摘要
Graphs are an important tool for modelling discrete structures. They are also known as networks, plans, diagrams or schemas. The wide use of graphs is based on the fact that there is a drawing.The planar graphs are the best known and mostly investigated class of graphs. However, most graphs are non-planar, particularly in applications. This has recently lead to the introduction of beyond-planar graphs. Such graphs have crossings in some regulated way, and they adopt important properties from planar graphs, such as as a linear number of edges and drawing algorithms. Planar graphs are commonly drawn straight line. There are orthogonal drawings with horizontal and vertical line segments and visibility representations, where vertices are represented by horizontal lines and edges by a vertical visibility between the respective vertices. Visibility representations are less common than straight-line drawings, but they are algorithmically easier and conceptually more flexible. There is an unexplored potentential behind visibility representations if crossings are allowed in some controlled way. Then visibility representations dominate convential drawing styles. They provide many options to define beyond-planar graphs. In this project we wish to explore this potential of visibility representations. In particular, we define new classes of beyond-planar graphs and shall investigate typical graph theoretic properties and the complexity of recognition problems. Moreover, we shall develop optimized graph drawing algorithms. Our studies shall help to develop beyond-planarity.
期刊论文(3)
专著(0)
科研奖励(0)
会议论文
Recognizing Optimal 1-Planar Graphs in Linear Time
识别线性时间内的最优一平面图
DOI: 10.1007/s00453-016-0226-8
发表时间:
期刊: Algorithmica
影响因子: 1.1
作者: [F. J. Brandenburg]
通讯作者: F. J. Brandenburg
DOI: 10.1016/j.tcs.2016.04.026
发表时间: 2015-09
期刊: Deep-sea Research Part Ii-topical Studies in Oceanography
影响因子: 3
作者: [F. Brandenburg;W. Didimo;W. Evans;Philipp Kindermann;G. Liotta;Fabrizio Montecchiani]
通讯作者: F. Brandenburg;W. Didimo;W. Evans;Philipp Kindermann;G. Liotta;Fabrizio Montecchiani
DOI: 10.1007/s00453-015-0002-1
发表时间: 2016-04
期刊: Algorithmica
影响因子: 1.1
作者: [Christopher Auer;C. Bachmaier;F. Brandenburg;Andreas Gleißner;Kathrin Hanauer;Daniel Neuwirth;Josef Reislhuber]
通讯作者: Christopher Auer;C. Bachmaier;F. Brandenburg;Andreas Gleißner;Kathrin Hanauer;Daniel Neuwirth;Josef Reislhuber
Ranking Probleme bei unvollständiger Information
  • 批准号:
    210423731
  • 项目类别:
    Research Grants
  • 资助金额:
    $0.0万
  • 财政年份:
    2012
  • 负责人:
    Professor Dr. Franz Josef Brandenburg
  • 依托单位:
Radiales und zyklisches Zeichnen von Graphen: Layouts auf dem Zylinder
  • 批准号:
    148338284
  • 项目类别:
    Research Grants
  • 资助金额:
    $0.0万
  • 财政年份:
    2009
  • 负责人:
    Professor Dr. Franz Josef Brandenburg
  • 依托单位:
Strukturiertes Clustern von Graphen und deren Visualisierung
  • 批准号:
    5279548
  • 项目类别:
    Research Grants
  • 资助金额:
    $0.0万
  • 财政年份:
    2000
  • 负责人:
    Professor Dr. Franz Josef Brandenburg
  • 依托单位:
Design, Analyse, Implementierung und experimentelle Anwendungen von Algorithmen zum Zeichnen von Graphen
  • 批准号:
    5215512
  • 项目类别:
    Priority Programmes
  • 资助金额:
    $0.0万
  • 财政年份:
    1995
  • 负责人:
    Professor Dr. Franz Josef Brandenburg
  • 依托单位:
海外基金