Optimal Orthogonal Drawings of Planar 3-Graphs in Linear Time

被引：0

作者：

Didimo, Walter ^{[1
]}

Liotta, Giuseppe ^{[1
]}

Ortali, Giacomo ^{[1
]}

Patrignani, Maurizio ^{[2
]}

机构：

[1] Univ Perugia, Dip Ingn, Via G Duranti 93, I-06125 Perugia, Italy

[2] Univ Roma Tre, Dip Ingn, Via Vasca Navale 79, I-00146 Rome, Italy

来源：

PROCEEDINGS OF THE 2020 ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, SODA | 2020年

关键词：

GRAPH;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

This paper addresses a long standing, widely studied, open question: Given a planar 3-graph G (i.e., a planar graph with vertex degree at most three), what is the best computational upper bound to compute a bend-minimum planar orthogonal drawing of G in the variable embedding setting? In this setting the algorithm can choose among the exponentially many planar embeddings of G the one that leads to an orthogonal drawing with the minimum number of bends. We answer the question by describing a linear-time algorithm that computes a bend-minimum planar orthogonal drawing of G. Also, if G is not K-4, the drawing has at most one bend per edge. The existence of an orthogonal drawing of a planar 3-graph such that Gamma has the minimum number of bends and at most one bend per edge was previously unknown.

引用

页码：806 / 825

页数：20

共 33 条

[11] Sketched Representations and Orthogonal Planarity of Bounded Treewidth Graphs
Di Giacomo, Emilio
Liotta, Giuseppe
Montecchiani, Fabrizio
[J]. GRAPH DRAWING AND NETWORK VISUALIZATION, 2019, 11904 : 379 - 392
[12] Bend-Minimum Orthogonal Drawings in Quadratic Time
Didimo, Walter
Liotta, Giuseppe
Patrignani, Maurizio
[J]. GRAPH DRAWING AND NETWORK VISUALIZATION, GD 2018, 2018, 11282 : 481 - 494
[13] Didimo W., 2007, Graph Visualization and Data Mining, P35
[14] Didimo W, 2020, PROCEEDINGS OF THE THIRTY-FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS (SODA'20), P806
[15] HV-planarity: Algorithms and complexity
Didimo, Walter
Liotta, Giuseppe
Patrignani, Maurizio
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2019, 99 : 72 - 90
[16] Eiglsperger M., 2004, Information Visualization, V3, P189, DOI 10.1057/palgrave.ivs.9500078
[17] On the computational complexity of upward and rectilinear planarity testing
Garg, A
Tamassia, R
[J]. SIAM JOURNAL ON COMPUTING, 2001, 31 (02) : 601 - 625
[18] Gutwenger C., 2001, LNCS, V1984, P77, DOI [10.1007/3-540-44541-28, DOI 10.1007/3-540-44541-28]
[19] No-Bend Orthogonal Drawings and No-Bend Orthogonally Convex Drawings of Planar Graphs (Extended Abstract)
Hasan, Md Manzurul
Rahman, Md Saidur
[J]. COMPUTING AND COMBINATORICS, COCOON 2019, 2019, 11653 : 254 - 265
[20] Hopcroft J. E., 1973, SIAM Journal on Computing, V2, P135, DOI 10.1137/0202012

← 1 2 3 4 →