Planar L-Drawings of Bimodal Graphs

被引：0

作者：

Angelini P. ^{[1
]}

Chaplick S. ^{[2
]}

Cornelsen S. ^{[3
]}

Da Lozzo G. ^{[4
]}

机构：

[1] John Cabot University, Rome

[2] Roma Tre University, Rome

来源：

Journal of Graph Algorithms and Applications | 2022年 / 26卷 / 03期

关键词：

Compendex;

D O I：

10.7155/jgaa.00596

中图分类号：

学科分类号：

摘要：

In a planar L-drawing of a directed graph (digraph) each edge e is represented as a polyline composed of a vertical segment starting at the tail of e and a horizontal segment ending at the head of e. Distinct edges may overlap, but not cross. Our main focus is on bimodal graphs, i.e., digraphs admitting a planar embedding in which the incoming and outgoing edges around each vertex are contiguous. We show that every plane bimodal graph without 2-cycles admits a planar L-drawing. This includes the class of upward-plane graphs. Bimodal graphs with 2-cycles admit a planar L-drawing if the underlying undirected graph with merged 2-cycles is a planar 3-tree. Finally, outerplanar digraphs admit a planar L-drawing – although they do not always have a bimodal embedding – but not necessarily with an outerplanar embedding. © 2022, Brown University. All rights reserved.

引用

页码：307 / 334

页数：27

共 23 条

[1]

Ahuja R. K., Magnanti T. L., Orlin J. B., Network Flows: Theory, Algorithms, and Applications, (1993)

[2]

Angelini P., Chaplick S., Cornelsen S., Da Lozzo G., On upward-planar L-drawings of graphs, (2022)

[3]

Angelini P., Da Lozzo G., Di Bartolomeo M., Di Donato V., Patrignani M., Roselli V., Tollis I. G., Algorithms and bounds for L-drawings of directed graphs, Int. J. Found. Comput. Sci, 29, 4, pp. 461-480, (2018)

[4]

Angelini P., Da Lozzo G., Di Battista G., Donato V. D., Kindermann P., Rote G., Rutter I., Windrose planarity: Embedding graphs with direction-constrained edges, ACM Trans. Algorithms, 14, 4, (2018)

[5]

Barth W., Mutzel P., Yildiz C., A new approximation algorithm for bend minimization in the Kandinsky model, GD 2006, volume 4372 of LNCS, pp. 343-354, (2007)

[6]

Besa Vial J. J., Da Lozzo G., Goodrich M. T., Computing k-modal embeddings of planar digraphs, ESA 2019, 144, (2019)

[7]

Bhasker J., Sahni S., A linear algorithm to find a rectangular dual of a planar triangulategraph, Algorithmica, 3, pp. 247-278, (1988)

[8]

Biedl T. C., Derka M., The (3,1)-ordering for 4-connected planar triangulations, JGAA, 20, 2, pp. 347-362, (2016)

[9]

Biedl T. C., Mondal D., A note on plus-contacts, rectangular duals, and box-orthogonal drawings, (2017)

[10]

Binucci C., Didimo W., Patrignani M., Upward and quasi-upward planarity testing of embedded mixed graphs, Theor. Comput. Sci, 526, pp. 75-89, (2014)

← 1 2 3 →