In this paper, we study drawings of directed
graphs. We use the L-drawing standard where each
edge is represented by a polygonal chain that
consists of a vertical line segment incident to the
source of the edge and a horizontal line segment
incident to the target. First, we consider
planar L-drawings. 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. We also show how to decide
in linear time whether there exists a planar
L-drawing of a plane directed graph with a fixed
assignment of the edges to the four sides (top,
bottom, left, and right) of the vertices. \par
Second, we consider upward- (resp.\
upward-rightward-) planar L-drawings. We provide
upper bounds on the maximum number of edges of
graphs admitting such drawings. Moreover, we
characterize the directed st-graphs admitting an
upward- (resp.\ upward-rightward-) planar L-drawing
as exactly those admitting an embedding supporting a
bitonic (resp.\ monotonically decreasing)
st-ordering.
%0 Journal Article
%1 cccdnptw-plddg-JGAA23
%A Chaplick, Steven
%A Chimani, Markus
%A Cornelsen, Sabine
%A Da Lozzo, Giordano
%A Nöllenburg, Martin
%A Patrignani, Maurizio
%A Tollis, Ioannis G.
%A Wolff, Alexander
%D 2023
%J Computing in Geometry and Topology
%K L-drawings NP-hard bitonic_st-ordering graph_drawing monotonically_decreasing_st-ordering myown planar_L-drawings
%N 1
%P 7:1--7:15
%R 10.57717/cgt.v2i1.43
%T Planar L-Drawings of Directed Graphs
%V 2
%X In this paper, we study drawings of directed
graphs. We use the L-drawing standard where each
edge is represented by a polygonal chain that
consists of a vertical line segment incident to the
source of the edge and a horizontal line segment
incident to the target. First, we consider
planar L-drawings. 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. We also show how to decide
in linear time whether there exists a planar
L-drawing of a plane directed graph with a fixed
assignment of the edges to the four sides (top,
bottom, left, and right) of the vertices. \par
Second, we consider upward- (resp.\
upward-rightward-) planar L-drawings. We provide
upper bounds on the maximum number of edges of
graphs admitting such drawings. Moreover, we
characterize the directed st-graphs admitting an
upward- (resp.\ upward-rightward-) planar L-drawing
as exactly those admitting an embedding supporting a
bitonic (resp.\ monotonically decreasing)
st-ordering.
@article{cccdnptw-plddg-JGAA23,
abstract = {In this paper, we study drawings of directed
graphs. We use the L-drawing standard where each
edge is represented by a polygonal chain that
consists of a vertical line segment incident to the
source of the edge and a horizontal line segment
incident to the target. \par First, we consider
planar L-drawings. 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. We also show how to decide
in linear time whether there exists a planar
L-drawing of a plane directed graph with a fixed
assignment of the edges to the four sides (top,
bottom, left, and right) of the vertices. \par
Second, we consider upward- (resp.\
upward-rightward-) planar L-drawings. We provide
upper bounds on the maximum number of edges of
graphs admitting such drawings. Moreover, we
characterize the directed st-graphs admitting an
upward- (resp.\ upward-rightward-) planar L-drawing
as exactly those admitting an embedding supporting a
bitonic (resp.\ monotonically decreasing)
st-ordering.},
added-at = {2024-04-29T21:12:31.000+0200},
author = {Chaplick, Steven and Chimani, Markus and Cornelsen, Sabine and {Da Lozzo}, Giordano and Nöllenburg, Martin and Patrignani, Maurizio and Tollis, Ioannis G. and Wolff, Alexander},
biburl = {https://www.bibsonomy.org/bibtex/2508ae871a91251b89cdf572809684efd/awolff},
doi = {10.57717/cgt.v2i1.43},
interhash = {41ef736a701dee1d6d47ef0db4da49a6},
intrahash = {508ae871a91251b89cdf572809684efd},
journal = {Computing in Geometry and Topology},
keywords = {L-drawings NP-hard bitonic_st-ordering graph_drawing monotonically_decreasing_st-ordering myown planar_L-drawings},
number = 1,
pages = {7:1--7:15},
timestamp = {2024-04-29T21:12:31.000+0200},
title = {Planar {L}-Drawings of Directed Graphs},
volume = 2,
year = 2023
}