1. Planar L-Drawings of Bimodal Graphs
- Author
-
Angelini, Patrizio, Chaplick, Steven, Cornelsen, Sabine, Lozzo, Giordano Da, Auber, David, Valtr, Pavel, Auber D.,Valtr P., Angelini, Patrizio, Chaplick, Steven, Cornelsen, Sabine, DA LOZZO, Giordano, Chaplick, Steve, Dept. of Advanced Computing Sciences, RS: FSE DACS, RS: FSE DACS Mathematics Centre Maastricht, and DKE Scientific staff
- Subjects
Computational Geometry (cs.CG) ,FOS: Computer and information sciences ,Vertex (graph theory) ,050101 languages & linguistics ,General Computer Science ,Discrete Mathematics (cs.DM) ,02 engineering and technology ,Computer Science::Computational Geometry ,Edge (geometry) ,Theoretical Computer Science ,Bimodality ,Combinatorics ,Planar ,Computer Science::Discrete Mathematics ,Computer Science - Data Structures and Algorithms ,0202 electrical engineering, electronic engineering, information engineering ,Planar L-drawings ,Data Structures and Algorithms (cs.DS) ,0501 psychology and cognitive sciences ,Mathematics ,Plane (geometry) ,Directed graph ,05 social sciences ,Digraph ,Computer Science Applications ,Computational Theory and Mathematics ,Computer Science - Computational Geometry ,Embedding ,020201 artificial intelligence & image processing ,Geometry and Topology ,Focus (optics) ,Computer Science - Discrete Mathematics - 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., Appears in the Proceedings of the 28th International Symposium on Graph Drawing and Network Visualization (GD 2020)
- Published
- 2022