Planar L-drawings of directed graphs

DOI10.1007/978-3-319-73915-1_36zbMATH Open1503.68212arXiv1708.09107OpenAlexW2963534320MaRDI QIDQ4625136FDOQ4625136

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)

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.

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

Recommendations

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

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)

Cites Work

• On-Line Planarity Testing
• On the computational complexity of upward and rectilinear planarity testing
• Algorithms for plane representations of acyclic digraphs
• Title not available (Why is that?)
• On the Complexity of HV-rectilinear Planarity Testing
• Complexity of Higher-Degree Orthogonal Graph Embedding in the Kandinsky Model
• Bitonic st-orderings of Biconnected Planar Graphs
• L-Drawings of Directed Graphs
• Planar L-Drawings of Directed Graphs
• Bitonic st-orderings for Upward Planar Graphs
• Overloaded orthogonal drawings
• A New Approximation Algorithm for Bend Minimization in the Kandinsky Model

Cited In (17)

• Planar L-Drawings of Bimodal Graphs
• Computing k-modal embeddings of planar digraphs
• Upward Book Embeddings of st-Graphs
• Planar Lombardi Drawings for Subcubic Graphs
• Planar Confluent Orthogonal Drawings of 4-Modal Digraphs
• Planar confluent orthogonal drawings of 4-modal digraphs
• Universal slope sets for upward planar drawings
• Upright-Quad Drawing of st-Planar Learning Spaces
• Bitonic \(st\)-orderings for upward planar graphs: splits and bends in the variable embedding scenario
• L-Drawings of Directed Graphs
• Upward book embeddability of \(st\)-graphs: complexity and algorithms
• Parameterized and approximation algorithms for the maximum bimodal subgraph problem
• Extending upward planar graph drawings
• Planar L-Drawings of Directed Graphs
• Planar L-Drawings of Bimodal Graphs
• 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)