Results 41 to 50 of about 1,027 (141)
Treewidth and pathwidth of permutation graphs [PDF]
SIAM Journal on Discrete Mathematics, 1993 This paper is the first one in a series of articles using scanlines in intersection models of graphs. The new concept enables to prove that every minimal triangulation of a permutation graph into a chordal graph is an interval graph, a result that generalizes to minimal triangulations of asteroidal-triple free graphs [Discrete Appl. Math.
Hans L. Bodlaender +2 more
openaire +4 more sources
Pole Dancing: 3D Morphs for Tree Drawings
Journal of Graph Algorithms and Applications, 2019 We study the question whether a crossing-free 3D morph between two straight-line drawings of an $n$-vertex tree $T$ can be constructed consisting of a small number of linear morphing steps. We look both at the case in which the two given drawings are two-
Elena Arseneva +7 more
doaj +1 more source
Parameterized Algorithms for Book Embedding Problems
Journal of Graph Algorithms and Applications, 2020 A $k$-page book embedding of a graph $G$ draws the vertices of $G$ on a line and the edges on $k$ half-planes (called pages) bounded by this line, such that no two edges on the same page cross. We study the problem of determining whether $G$ admits a $k$-
Sujoy Bhore +3 more
doaj +1 more source
On edge-intersection graphs of k-bend paths in grids [PDF]
Discrete Mathematics & Theoretical Computer Science, 2010 Edge-intersection graphs of paths in grids are graphs that can be represented such that vertices are paths in a grid and edges between vertices of the graph exist whenever two grid paths share a grid edge. This type of graphs is motivated by applications
Therese Biedl, Michal Stern
doaj +1 more source
On Approximating Cutwidth and Pathwidth
2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)We study graph ordering problems with a min-max objective. A classical problem of this type is cutwidth, where given a graph we want to order its vertices such that the number of edges crossing any point is minimized. We give a $ \log^{1+o(1)}(n)$ approximation for the problem, substantially improving upon the previous poly-logarithmic guarantees based
Nikhil Bansal 0001 +2 more
openaire +3 more sources
1-Planarity of Graphs with a Rotation System
Journal of Graph Algorithms and Applications, 2015 A graph is 1-planar if it can be drawn in the plane such that each edge is crossed at most once. 1-planarity is known NP-hard, even for graphs of bounded bandwidth, pathwidth, or treewidth, and for near-planar graphs in which an edge is added to a planar
Christopher Auer +3 more
doaj +1 more source
Exclusive graph searching vs. pathwidth [PDF]
, 2017 In Graph Searching, a team of searchers aims at capturing an invisible fugitive moving arbitrarily fast in a graph. Equivalently, the searchers try to clear a contaminated network.
Markou E., Nisse N., Pérennes S.
core +2 more sources
Pathwidth of 2-Layer k-Planar Graphs
Computing in Geometry and TopologyA bipartite graph G = (X ∪ Y, E) is a 2-layer k-planar graph if it admits a drawing on the plane such that the vertices in X and Y are placed on two parallel lines respectively, edges are drawn as straight-line segments, and every edge involves at most ...
Yuto Okada
doaj +1 more source
Semantic Tree-Width and Path-Width of Conjunctive Regular Path Queries [PDF]
Logical Methods in Computer ScienceWe show that the problem of whether a query is equivalent to a query of tree-width $k$ is decidable, for the class of Unions of Conjunctive Regular Path Queries with two-way navigation (UC2RPQs).
Diego Figueira, Rémi Morvan
doaj +1 more source
Parameterized Complexity of Safe Set
Journal of Graph Algorithms and Applications, 2020 In this paper we study the problem of finding a small safe set $S$ in a graph $G$, i.e., a non-empty set of vertices such that no connected component of $G[S]$ is adjacent to a larger component in $G - S$. We enhance our understanding of the problem from
Rémy Belmonte +5 more
doaj +1 more source