Orthogonal and Smooth Orthogonal Layouts of 1-Planar Graphs with Low Edge Complexity

被引：0

作者：

Argyriou, Evmorfia ^{[1
]}

Cornelsen, Sabine ^{[2
]}

Foerster, Henry ^{[3
]}

Kaufmann, Michael ^{[3
]}

Nollenburg, Martin ^{[4
]}

Okamoto, Yoshio ^{[5
]}

Raftopoulou, Chrysanthi ^{[6
]}

Wolff, Alexander ^{[7
]}

机构：

[1] yWorks GmbH, Tubingen, Germany

[2] Univ Konstanz, Constance, Germany

[3] Univ Tubingen, Tubingen, Germany

[4] TU Wien, Vienna, Austria

[5] Univ Electrocommun, RIKEN, Ctr Adv Intelligence Project, Chofu, Tokyo, Japan

[6] Natl Tech Univ Athens, Athens, Greece

[7] Univ Wurzburg, Wurzburg, Germany

来源：

GRAPH DRAWING AND NETWORK VISUALIZATION, GD 2018 | 2018年 / 11282卷

关键词：

D O I：

10.1007/978-3-030-04414-5_36

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

While orthogonal drawings have a long history, smooth orthogonal drawings have been introduced only recently. So far, only planar drawings or drawings with an arbitrary number of crossings per edge have been studied. Recently, a lot of research effort in graph drawing has been directed towards the study of beyond-planar graphs such as 1-planar graphs, which admit a drawing where each edge is crossed at most once. In this paper, we consider graphs with a fixed embedding. For 1-planar graphs, we present algorithms that yield orthogonal drawings with optimal curve complexity and smooth orthogonal drawings with small curve complexity. For the subclass of outer-1-planar graphs, which can be drawn such that all vertices lie on the outer face, we achieve optimal curve complexity for both, orthogonal and smooth orthogonal drawings.

引用

页码：509 / 523

页数：15

共 24 条

[1] Alam Md Jawaherul, 2013, Graph Drawing. 21st International Symposium, GD 2013. Revised Selected Papers: LNCS 8242, P83, DOI 10.1007/978-3-319-03841-4_8
[2] Alam MJ, 2014, LECT NOTES COMPUT SC, V8392, P144
[3] [Anonymous], 2012, J GRAPH ALGORITHMS A, DOI DOI 10.7155/JGAA.00251
[4] Argyriou E, 2018, ORTHOGONAL SMOOTH OR ORTHOGONAL SMOOTH OR
[5] Outer 1-Planar Graphs
Auer, Christopher
Bachmaier, Christian
Brandenburg, Franz J.
Gleissner, Andreas
Hanauer, Kathrin
Neuwirth, Daniel
Reislhuber, Josef
[J]. ALGORITHMICA, 2016, 74 (04) : 1293 - 1320
[6] Bekos MA, 2014, 5TH INTERNATIONAL CONFERENCE ON INFORMATION, INTELLIGENCE, SYSTEMS AND APPLICATIONS, IISA 2014, P76, DOI 10.1109/IISA.2014.6878731
[7] Bekos M.A., 2013, J GRAPH ALGORITHMS A, V17, P575, DOI [10.7155/jgaa.00305, DOI 10.7155/JGAA.00305]
[8] A better heuristic for orthogonal graph drawings
Biedl, T
Kant, G
[J]. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 1998, 9 (03): : 159 - 180
[9] Brandenburg Franz J., 2014, Journal of Graph Algorithms and Applications, V18, P421, DOI 10.7155/jgaa.00330
[10] EVERY OUTER-1-PLANE GRAPH HAS A RIGHT ANGLE CROSSING DRAWING
Dehkordi, Hooman Reisi
Eades, Peter
[J]. INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 2012, 22 (06) : 543 - 557

← 1 2 3 →