1,721,083 research outputs found
On Upward-Planar L-Drawings of Graphs
Full text linkIn an upward-planar L-drawing of a directed acyclic graph (DAG) each edge e = (v, w) is represented as a polyline composed of a vertical segment with its lowest endpoint at the tail v of e and of a horizontal segment ending at the head w of e. Distinct edges may overlap, but must not cross. Recently, upward-planar L-drawings have been studied for st-graphs, i.e., planar DAGs with a single source s and a single sink t containing an edge directed from s to t. It is known that a plane st-graph, i.e., an embedded st-graph in which the edge (s, t) is incident to the outer face, admits an upward-planar L-drawing if and only if it admits a bitonic st-ordering, which can be tested in linear time. We study upward-planar L-drawings of DAGs that are not necessarily st-graphs. As a combinatorial result, we show that a plane DAG admits an upward-planar L-drawing if and only if it is a subgraph of a plane st-graph admitting a bitonic st-ordering. This allows us to show that not every tree with a fixed bimodal embedding admits an upward-planar L-drawing. Moreover, we prove that any directed acyclic cactus with a single source (or a single sink) admits an upward-planar L-drawing, which respects a given outerplanar embedding if there are no transitive edges. On the algorithmic side, we consider DAGs with a single source (or a single sink). We give linear-time testing algorithms for these DAGs in two cases: (a) when the drawing must respect a prescribed embedding and (b) when no restriction is given on the embedding, but the underlying undirected graph is series-parallel. For the single-sink case of (b) it even suffices that each biconnected component is series-parallel.</p
Planar Drawings with Few Slopes of Halin Graphs and Nested Pseudotrees
No full textThe planar slope numberpsn(G) of a planar graph G is the minimum number of edge slopes in a planar straight-line drawing of G. It is known that psn(G)∈O(cΔ) for every planar graph G of maximum degree Δ. This upper bound has been improved to O(Δ5) if G has treewidth three, and to O(Δ) if G has treewidth two. In this paper we prove psn(G)≤max{4,Δ} when G is a Halin graph, and thus has treewidth three. Furthermore, we present the first polynomial upper bound on the planar slope number for a family of graphs having treewidth four. Namely we show that O(Δ2) slopes suffice for nested pseudotrees.</p
Planar L-Drawings of Bimodal Graphs
No full textIn 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
The partial visibility representation extension problem
Full text linkFor a graph G, a function ψ is called a bar visibility representation of G when for each vertex v∈V(G), ψ(v) is a horizontal line segment (bar) and uv∈E(G) iff there is an unobstructed, vertical, ε-wide line of sight between ψ(u) and ψ(v). Graphs admitting such representations are well understood (via simple characterizations) and recognizable in linear time. For a directed graph G, a bar visibility representation ψ of G, additionally, for each directed edge (u, v) of G, puts the bar ψ(u) strictly below the bar ψ(v). We study a generalization of the recognition problem where a function ψ′ defined on a subset V′ of V(G) is given and the question is whether there is a bar visibility representation ψ of G with ψ|V′=ψ′. We show that for undirected graphs this problem together with closely related problems are NP
-complete, but for certain cases involving directed graphs it is solvable in polynomial time
Planar L-Drawings of Directed Graphs
No full textIn 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.
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.publishe
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Variations on the Author
Full text link“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
Morphing Contact Representations of Graphs
Full text linkWe consider the problem of morphing between contact representations of a plane graph. In a contact representation of a plane graph, vertices are realized by internally disjoint elements from a family of connected geometric objects. Two such elements touch if and only if their corresponding vertices are adjacent. These touchings also induce the same embedding as in the graph. In a morph between two contact representations we insist that at each time step (continuously throughout the morph) we have a contact representation of the same type.
We focus on the case when the geometric objects are triangles that are the lower-right half of axis-parallel rectangles. Such RT-representations exist for every plane graph and right triangles are one of the simplest families of shapes supporting this property. Thus, they provide a natural case to study regarding morphs of contact representations of plane graphs.
We study piecewise linear morphs, where each step is a linear morph moving the endpoints of each triangle at constant speed along straight-line trajectories. We provide a polynomial-time algorithm that decides whether there is a piecewise linear morph between two RT-representations of a plane triangulation, and, if so, computes a morph with a quadratic number of linear morphs. As a direct consequence, we obtain that for 4-connected plane triangulations there is a morph between every pair of RT-representations where the "top-most" triangle in both representations corresponds to the same vertex. This shows that the realization space of such RT-representations of any 4-connected plane triangulation forms a connected set
- …
