In a planar L-drawing of a directed graph (digraph) each edge e e is represented as a polyline composed of a vertical segment starting at the tail of e e and a horizontal segment ending at the head of e 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.

Angelini, P., Chaplick, S., Cornelsen, S., DA LOZZO, G. (2022). Planar L-Drawings of Bimodal Graphs. JOURNAL OF GRAPH ALGORITHMS AND APPLICATIONS, 26(3), 307-334 [10.7155/jgaa.00596].

Planar L-Drawings of Bimodal Graphs

Angelini Patrizio;Da Lozzo Giordano
2022-01-01

Abstract

In a planar L-drawing of a directed graph (digraph) each edge e e is represented as a polyline composed of a vertical segment starting at the tail of e e and a horizontal segment ending at the head of e 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.
Angelini, P., Chaplick, S., Cornelsen, S., DA LOZZO, G. (2022). Planar L-Drawings of Bimodal Graphs. JOURNAL OF GRAPH ALGORITHMS AND APPLICATIONS, 26(3), 307-334 [10.7155/jgaa.00596].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11590/426891
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact