1,721,078 research outputs found
Clustered Planarity with Pipes
No full textWe study the version of the C-Planarity problem in which edges connecting the same pair of clusters must be grouped into pipes, which generalizes the Strip Planarity problem. We give algorithms to decide several families of instances for the two variants in which the order of the pipes around each cluster is given as part of the input or can be chosen by the algorithm
Clustered Planarity with Pipes
Full text linkWe study the version of the C-Planarity problem in which edges connecting the same pair of clusters must be grouped into pipes, which generalizes the Strip Planarity problem. We give algorithms to decide several families of instances for the two variants in which the order of the pipes around each cluster is given as part of the input or can be chosen by the algorithm
2-Layer k-Planar Graphs Density, Crossing Lemma, Relationships And Pathwidth
Full text linkThe 2-layer drawing model is a well-established paradigm to visualize bipartite graphs where vertices of the two parts lie on two horizontal lines and edges lie between these lines. Several beyond-planar graph classes have been studied under this model. Surprisingly, however, the fundamental class of k-planar graphs has been considered only for k = 1 in this context. We provide several contributions that address this gap in the literature.First, we show tight density bounds for the classes of 2-layer k-planar graphs with k ? {2, 3, 4, 5}. Based on these results, we provide a Crossing Lemma for 2-layer k-planar graphs, which then implies a general density bound for 2-layer k-planar graphs. We prove this bound to be almost optimal with a corresponding lower bound construction. Finally, we study relationships between k-planarity and h-quasiplanarity in the 2-layer model and show that 2-layer k-planar graphs have pathwidth at most k + 1 while there are also 2-layer k-planar graphs with pathwidth at least (k + 3)/2
Planar L-Drawings of Bimodal Graphs
No full textIn a planar L-drawing of a directed graph (digraph) each edge
e
e
is represented as a polyline composed of a vertical segment starting at the tail of
e
e
and a horizontal segment ending at the head of
e
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. Bimodal graphs with 2-cycles admit a planar L-drawing if the underlying undirected graph with merged 2-cycles is a planar 3-tree. Finally, outerplanar digraphs admit a planar L-drawing - although they do not always have a bimodal embedding - but not necessarily with an outerplanar embedding
- …
