Planar L-Drawings of Bimodal Graphs

Authors

  • Patrizio Angelini
  • Steven Chaplick
  • Sabine Cornelsen
  • Giordano Da Lozzo

DOI:

https://doi.org/10.7155/jgaa.00596

Keywords:

Planar L-Drawings , Directed Graphs , Bimodality

Abstract

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.

Downloads

Download data is not yet available.

Downloads

Published

2022-06-01

How to Cite

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. https://doi.org/10.7155/jgaa.00596