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. 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. (2020). Planar L-Drawings of Bimodal Graphs. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp.205-219). Springer Science and Business Media Deutschland GmbH [10.1007/978-3-030-68766-3_17].

Planar L-Drawings of Bimodal Graphs

Angelini Patrizio;Da Lozzo Giordano
2020

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. Finally, outerplanar digraphs admit a planar L-drawing – although they do not always have a bimodal embedding – but not necessarily with an outerplanar embedding.
978-3-030-68765-6
Angelini, P., Chaplick, S., Cornelsen, S., DA LOZZO, G. (2020). Planar L-Drawings of Bimodal Graphs. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp.205-219). Springer Science and Business Media Deutschland GmbH [10.1007/978-3-030-68766-3_17].
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/386170
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact