7,609 research outputs found
Recognizing Proper Tree-Graphs
Full text linkWe investigate the parameterized complexity of the recognition problem for the proper H-graphs. The H-graphs are the intersection graphs of connected subgraphs of a subdivision of a multigraph H, and the properness means that the containment relationship between the representations of the vertices is forbidden. The class of H-graphs was introduced as a natural (parameterized) generalization of interval and circular-arc graphs by Biró, Hujter, and Tuza in 1992, and the proper H-graphs were introduced by Chaplick et al. in WADS 2019 as a generalization of proper interval and circular-arc graphs. For these graph classes, H may be seen as a structural parameter reflecting the distance of a graph to a (proper) interval graph, and as such gained attention as a structural parameter in the design of efficient algorithms. We show the following results.
- For a tree T with t nodes, it can be decided in 2^{(t² log t)} ⋅ n³ time, whether an n-vertex graph G is a proper T-graph. For yes-instances, our algorithm outputs a proper T-representation. This proves that the recognition problem for proper H-graphs, where H required to be a tree, is fixed-parameter tractable when parameterized by the size of T. Previously only NP-completeness was known.
- Contrasting to the first result, we prove that if H is not constrained to be a tree, then the recognition problem becomes much harder. Namely, we show that there is a multigraph H with 4 vertices and 5 edges such that it is NP-complete to decide whether G is a proper H-graph
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
Monotone Arc Diagrams with Few Biarcs
Full text linkWe show that every planar graph has a monotone topological 2-page book embedding where at most (4n-10)/5 (of potentially 3n-6) edges cross the spine, and every edge crosses the spine at most once; such an edge is called a biarc. We can also guarantee that all edges that cross the spine cross it in the same direction (e.g., from bottom to top). For planar 3-trees we can further improve the bound to (3n-9)/4, and for so-called Kleetopes we obtain a bound of at most (n-8)/3 edges that cross the spine. The bound for Kleetopes is tight, even if the drawing is not required to be monotone. A Kleetope is a plane triangulation that is derived from another plane triangulation T by inserting a new vertex v_f into each face f of T and then connecting v_f to the three vertices of f
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
Steven Johnson Author Talk Poster
No full textK-State Book NetworkA poster advertising an author talk by Steven Johnson at Kansas State University on September 3, 2014. Steven Johnson's book "The Ghost Map" was the 2014-2015 common book
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
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
Brief Announcement: Approximation Schemes for Geometric Coverage Problems
Full text linkIn this announcement, we show that the classical Maximum Coverage problem (MC) admits a PTAS via local search in essentially all cases where the corresponding instances of Set Cover (SC) admit a PTAS via the local search approach by Mustafa and Ray [Nabil H. Mustafa and Saurabh Ray, 2010]. As a corollary, we answer an open question by Badanidiyuru, Kleinberg, and Lee [Ashwinkumar Badanidiyuru et al., 2012] regarding half-spaces in R^3 thereby settling the existence of PTASs for essentially all natural cases of geometric MC problems. As an intermediate result, we show a color-balanced version of the classical planar subdivision theorem by Frederickson [Greg N. Frederickson, 1987]. We believe that some of our ideas may be useful for analyzing local search in other settings involving a hard cardinality constraint
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
On Upward-Planar L-Drawings of Graphs
Full text linkIn an upward-planar L-drawing of a directed acyclic graph (DAG) each edge
is represented as a polyline composed of a vertical segment with its lowest
endpoint at the tail of and of a horizontal segment ending at the head of
. Distinct edges may overlap, but not cross. Recently, upward-planar
L-drawings have been studied for -graphs, i.e., planar DAGs with a single
source and a single sink containing an edge directed from to .
It is known that a plane -graph, i.e., an embedded -graph in which the
edge is incident to the outer face, admits an upward-planar L-drawing
if and only if it admits a bitonic -ordering, which can be tested in linear
time.
We study upward-planar L-drawings of DAGs that are not necessarily
-graphs. On the combinatorial side, we show that a plane DAG admits an
upward-planar L-drawing if and only if it is a subgraph of a plane -graph
admitting a bitonic -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 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: (i) when the drawing must respect a prescribed
embedding and (ii) when no restriction is given on the embedding, but it is
biconnected and series-parallel.Comment: Extended abstract appeared at MFCS 202
- …
