Planar L-drawings of directed graphs

DOI10.1007/978-3-319-73915-1_36MaRDI QIDQ4625136zbMATH OpenOpenAlexFDO

Authors Steven Chaplick, Markus Chimani, Sabine Cornelsen, Giordano Da Lozzo, Martin Nöllenburg, Maurizio Patrignani, Alexander Wolff, Ioannis G. Tollis

Publication date 20 February 2019

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1708.09107

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: We study planar drawings of directed graphs in the L-drawing standard. We provide necessary conditions for the existence of these drawings and show that testing for the existence of a planar L-drawing is an NP-complete problem. Motivated by this result, we focus on upward-planar L-drawings. We show that directed st-graphs admitting an upward- (resp. upward-rightward-) planar L-drawing are exactly those admitting a bitonic (resp. monotonically increasing) st-ordering. We give a linear-time algorithm that computes a bitonic (resp. monotonically increasing) st-ordering of a planar st-graph or reports that there exists none.

Recommendations

• L-Drawings of Directed Graphs
• Algorithms and bounds for L-drawings of directed graphs
• scientific article; zbMATH DE number 68923
• Bitonic \(st\)-orderings for upward planar graphs
• Planar L-drawings of bimodal graphs

Cites work

• scientific article; zbMATH DE number 177843 (Why is no real title available?)
• A New Approximation Algorithm for Bend Minimization in the Kandinsky Model
• Algorithms for plane representations of acyclic digraphs
• Bitonic \(st\)-orderings for upward planar graphs
• Bitonic \(st\)-orderings of biconnected planar graphs
• Complexity of higher-degree orthogonal graph embedding in the Kandinsky model
• L-Drawings of Directed Graphs
• On the complexity of HV-rectilinear planarity testing
• On the computational complexity of upward and rectilinear planarity testing
• On-Line Planarity Testing
• Overloaded orthogonal drawings
• Planar L-drawings of directed graphs

Cited in

(21)

• Planar L-Drawings of Bimodal Graphs
• Computing k-modal embeddings of planar digraphs
• Drawing two posets
• Planar Lombardi Drawings for Subcubic Graphs
• Algorithms and bounds for L-drawings of directed graphs
• Planar L-drawings of directed graphs
• Planar Confluent Orthogonal Drawings of 4-Modal Digraphs
• Planar L-drawings of directed graphs
• Planar confluent orthogonal drawings of 4-modal digraphs
• Planar L-drawings of bimodal graphs
• Universal slope sets for upward planar drawings
• Upright-Quad Drawing of st-Planar Learning Spaces
• Bitonic \(st\)-orderings for upward planar graphs
• Bitonic \(st\)-orderings for upward planar graphs: splits and bends in the variable embedding scenario
• L-Drawings of Directed Graphs
• Upward book embeddings of st-graphs
• Upward book embeddability of \(st\)-graphs: complexity and algorithms
• On upward-planar L-drawings of graphs
• Parameterized and approximation algorithms for the maximum bimodal subgraph problem
• Universal slope sets for upward planar drawings
• Upright-Quad Drawing of st-Planar Learning Spaces

This page was built for publication: Planar L-drawings of directed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4625136)